3

我需要合并两个变量。它们都是无符号整数。

  • 第一：11000000
  • 二：11111010000

期望输出：11011111010000

用文字表示：我需要将所有 1 后跟一个 0（在第一个数字中）放在整个第二个数字的前面。我想到的唯一想法是，将第一个数字向左移位与第二个数字的长度一样多。而不是总结它。但我不知道长度。虽然它可能可以找到，但没有更好的更简单的方法吗？

谢谢

4

3 回答 3

2

这是一个在恒定时间内运行的解决方案：

您可以通过 (int)(log(x)/log(2)) 计算 x 的前 1 位的位置。

此外，您可以通过此处显示的巧妙技巧计算 x 的尾随零的数量：http: //graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

因此，您的程序可能看起来像这样：

int x, y;
int lookuptable[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25,
                        17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 
                        12, 18, 6, 11, 5, 10, 9 };

int tail_x = lookuptable[(((x & -x) * 0x077CB531U)) >> 27];
int size_y = (int)(log(y) / log(2)) + 1;

if (tail_x - size_y <= 0) {
        x <<= size_y - tail_x + 1;
} else {
        x >>= tail_x - size_y - 1;
}       

x |= y;

现在，x 包含将 y 附加到 OP 指定的 x 的结果。请注意，您需要对非 32 位机器进行微调。

于 2011-03-20T14:32:51.167 回答
1

将第一个向右位移，直到您有一系列 1，没有尾随 0。然后将其位移到左侧，以获得第二个加 1 的“长度”（实际上是在第一个 1 之后并包括第一个 1 之后的位数）和然后将它们组合在一起，不要求和，否则可能会出现错误。

于 2011-03-20T14:22:17.693 回答
0

确定整数是否为 2 的幂

无符号整数 v; // 我们想看看 v 是否是 2 的幂 bool f; // 结果在这里

f = (v & (v - 1)) == 0; 请注意，此处将 0 错误地视为 2 的幂。要解决此问题，请使用： f = v && !(v & (v - 1));

因此，要查看 v 是否小于 2 的幂，我们将 v (v + 1) & v) == 0 加一

(复制 + 1) & 复制) != 0

因此，使用乔恩的答案并将 copy!=0 替换为 (copy + 1) & copy) != 0 将修剪直到最后有一个带有一系列 1 的 int 。副本的范围需要在 for 循环之外，结果将是 (copy << (cBitsFirst + 1)) | 第二;

unsigned int first, second; // initialize these somehow
unsigned int result = 0;
int cBitsFirst = 0;
unsigned int copy;
for (copy; (copy + 1) & copy) != 0; copy >>= 1) {//stop when there is series of 0's followed by a series of 1's
    ++cBitsFirst;
}

result = (copy << (log2(second)+1) | second;//the plus one gives the 0 back
于 2011-03-20T14:55:41.877 回答