连接两个位模式

Question

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

• 第一个:11000000
• 第二个:11111010000

期望的输出:11011111010000

换句话说:我需要在整个第二个数字前面加上所有 1 和一个 0(在第一个数字中)。我想到的唯一想法是，将第一个数字向左移动与第二个数字的长度一样多。而不是总结它。但是我不知道长度。虽然可能可以找到，但是没有更好更简单的方法吗？

谢谢

Answer 1

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

您可以通过 (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 位机器，您需要稍作调整。