标签: bit-manipulation

我需要确定一个有符号的 32 位数字是否是 2 的幂。到目前为止，我知道要做的第一件事是检查它是否为负数，因为负数不能是 2 的幂。然后我需要查看下一个数字是否有效等等......所以我可以这样写：

// Return 1 if x is a power of 2, and return 0 otherwise.
int func(int x)
{
     return ((x != 0) && ((x & (~x + 1)) == x));
}

但是对于我的任务，我只能使用其中的 20 个运算符：

! ~ & ^ | + << >>

并且没有相等语句或循环或强制转换或语言结构。

所以我试图转换相等部分，我知道 !(a^b) 与 a == b 相同，但我似乎无法完全弄清楚。关于如何将其转换为允许的运营商的任何想法？

如何在 Java 中获取所有 64 位字符串作为字符串？

所以我想做这样的事情 -

long value = 10;
String bits = getBits(value);
System.out.println(bits);

我想输出将是

0000...1010 (64 bits)

不，这不是家庭作业！:)

我想将前 3 位从一个字节传输到另一个字节。目前我使用以下但它太慢了（不正确的分支预测会减慢速度）>

    byte newByte = 0;
    if(((oldByte >> 0)&1) == 1)  newByte |= 1 << 0;
    if(((oldByte >> 1)&1) == 1)  newByte |= 1 << 1;
    if(((oldByte >> 2)&1) == 1)  newByte |= 1 << 2;

如何在没有 if 语句或循环的单个操作中执行此操作？

注意：除了 bit num 3 之外的其他位可能会或可能不会在 oldByte 中设置，但我想忽略它们。

我尝试使用 newByte |= oldByte 但它传输的设置位超出了第 3 位，这不是我想要的。

有任何想法吗？

我有一个std::uint32_t，想要检查是否设置了确切的一位。如何在不遍历所有位的情况下执行此操作？换句话说，可以简化以下功能吗？

static inline bool isExactlyOneBitSet(std::uint32_t bits)
{
    return ((bits & 1) == bits
        || (bits & 1 << 1) == bits
        || (bits & 1 << 2) == bits
        // ...
        || (bits & 1 << 31) == bits
        );
}

奖励：如果返回值是找到的一位或为0，那将是很好的。

static inline bool isExactlyOneBitSet(std::uint32_t bits)
{
if (bits & 1) {return 1;}
else if  (bits & 1 << 1) {return 1 << 1;};
//...
else if  (bits & 1 << 31) {return 1 << 31;};

return …

我对C很新,我试图理解CI中的按位运算符在我面前找到这个代码(将2转换为37)

int main(void)
{
    int x = 2;
    x = (x<<x<<x) | (x<<x<<x) | (x << !!x) | !!x ;
    printf("%d\n" , x );  // prints 37 
}

现在这是我第一次看到这样的东西 (x<<x<<x),我不明白它在做什么.任何人都可以详细解释代码中的第二行吗？

让我们说我正在检查奇数:

(i % 2 == 1)

编译器是否会将该操作转换为:

if(a & 1)

？

我知道按位操作更快,有时我会使用位.

但是我的问题是:如果正常的算术更具可读性(在大多数情况下),如果编译器稍后可以转换它,我何时应该使用bitwise？

或者我总是在有可能的时候使用bitwise(即使它不太可读)？

如果我有一个xtype int，如何获取xLSB 的值并将数字中的所有其他位设置为该LSB？

我一直在与位运算符和逻辑运算符打交道，这有点（没有双关语），我知道它们是如何工作的。

移位运算符x >> 3和x << 3左，右分别×3位的位移位，我知道我们可以使用运营商如^ |和&为瞎搞与操纵位。我在理解此特定问题的逻辑时遇到了麻烦。

编辑：我们被允许用于此的运算符是！〜＆^ | + << >>

刚才我看到这个：

这就是一个叫做霍夫曼编码的真正聪明的想法出现的地方！这个想法是我们用如下代码表示字符（例如a，b，c，d，...）。

a: 00
b: 010
c: 011
d: 1000
e: 1001
f: 1010
g: 1011
h: 1111

Run Code Online (Sandbox Code Playgroud)

如果仔细看这些，您会发现一些特别的地方！这些代码都不是任何其他代码的前缀。因此，如果我们写下来，010001001011我们可以看到它是010 00 1001 011或baec！有没有任何歧义，因为0和01和0100没有任何意义。

我领会了这一要点，但我不明白（a）它是如何被发现的，以及（b）您如何知道它是如何工作的，或者（c）它到底是什么意思。此行具体描述了它：

因此，如果我们写下来，010001001011我们可以看到它是010 00 1001 011...。

我看到这些是代码，但我不明白您怎么知道不以的形式阅读0100 01 0010 11。我看到这些值实际上不是表中的代码。但是，我看不出您将如何解决这个问题！我想知道如何发现这一点。如果我试图修改这样的代码和位，我会这样做：

1. 提出一组代码，例如 10 100 1000 101 1001
2. 尝试写出一些代码示例。因此，也许一个示例只是按上述顺序连接代码：1010010001011001。
3. 看看我是否可以解析代码。所以10还是哎呀，没了101还... Darnit，那也许是因为我可以优先添加到代码的解析，所以10比更高的优先级101。那让我10 100 1000 10 x不知道最后10个应该是101。Dangit。

因此，我将尝试添加诸如优先级功能之类的其他功能，或目前我无法想到的其他功能，以查看它是否有助于解决问题。

我无法想象他们会如何发现霍夫曼编码中的这些代码可以被唯一地解析（我仍然看不到它，它实际上是如何实现的，我必须写一些示例才能看到它，或者。 …

当我在GCC中编译此代码段时：

uint8_t *reg = ..., newflags = ...;
...
if(*reg == (~(uint8_t)0))
{
    newflags |= (1<<2);
    newflags |= (1<<7);
}

我收到此警告： warning: comparison is always false due to limited range of data type [-Wtype-limits]

reg和newflags分别是uint8_t *和uint8_t类型。

这是什么意思？而我该如何解决呢？

如果两个整数x和y的按位与的结果等于0，则它们构成一个魔幻对。给定一个整数数组，请为每个数组元素查找是否与其他数组元素形成了魔幻对。

输入项

输入的第一行包含一个整数T，表示测试用例的数量。每个测试用例的第一行都有一个整数N，表示给定数组中元素的数量。第二行包含N个单个以空格分隔的整数a1，a2，...，表示给定数组的元素。

输出量

对于每个测试用例，在一行中打印N个空格分隔的整数。如果ai与给定数组的任何其他元素形成一个魔幻对，则ans'i应该等于1。否则ans'i为0。

约束条件

1 <= N，Ai <= 10 ^ 6

我尝试过蛮力。对于每个元素，我检查此数字的按位与是否为零，或者是否与数组中存在的任何其他元素相同。显然，它的时间复杂度为O（N ^ 2），我的大多数测试用例都超时了

这个问题在这里：https : //www.hackerearth.com/challenges/test/netapp-codenet-2017/algorithm/d2d1f6a92c6740278682e88ed42068a4/

谁能建议我一个更好的方法或算法，使其超过时间限制？

蛮力代码：

int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
    cin >> a[i];
int ans[n];
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (a[i] & a[j] == 0)
            ans[i] = 1;
for (int i = 0; i < n; i++)
    cout …