设置第一个“1”之前的所有位

Question

假设一个 32 位无符号整数（答案当然可以推广到任何大小更好）。

这个整数可以假设为2的幂，因此只设置了一位。 我想设置整数中的所有位，除了那些低于设置位的位。因此（为简洁起见，使用 8 位整数）

00001000

将变为

11111000

。

这当然可以通过找到一个设置位然后迭代较高位并设置它们来完成。假设

highest_set

返回最高设置位的位置：

uint32_t f(uint32_t x)
{
  int n = highest_set(x);
  for (int i = 31; i != n; --i) {
      x |= 1 << i;
  }
  return x;
}

f

的运行时间确实取决于

x

的值，我觉得有一种更聪明的方法可以做到这一点。

Answer 1

从概念上讲，一个简单的做法是采用

x - 1

，然后与

0xffffffff

进行异或。正如 harold 在下面的评论中所做的那样将其写为

~(x - 1)

将处理不同大小的整数，而无需更改您要进行异或运算的内容。

Answer 2

右移 log(值), OR 位掩码为 1， 左移日志（值）。 这应该是一个通用的解决方案，对于任何输入都具有相同的运行时间，但不能保证。

Answer 3

你只需要取二进制补码

x = -x;

无论 x 有符号还是无符号都有效

为什么？因为您所做的本质上是将数字转换为 2 的补码的快速方法

手动将二进制数转换为二进制补码的捷径是从最低有效位开始（LSB），然后复制所有零（从LSB到最高有效位）直到达到第一个1 ;然后复制该 1，并翻转所有剩余的位

https://en.wikipedia.org/wiki/Two%27s_complement#Working_from_LSB_towards_MSB

你只有一个位集，所以当你复制所有零位并反转剩余的零位时，你会得到它的2的补码。您可以在示例中看到它：

00001000 = 8, 11111000 = -8

。其他一些例子：

00010000 = 16, 11110000 = -16
00100000 = 32, 11100000 = -32
01000000 = 64, 11000000 = -64

---

如果 x 是 signed 类型，那么很容易理解。对于 unsigned 类型，显然没有负值，因此它的工作原理是 C 标准如何定义无符号运算

涉及无符号操作数的计算永远不会溢出，因为无法由结果无符号整数类型表示的结果会以比结果类型可以表示的最大值大一的数为模进行缩减。

这只是2的补码的另一个定义，因为比结果类型可以表示的最大值大的一个（即本例中的

UINTN_MAX + 1

）是2^N。在 C 中，对无符号值取反总是会产生其补码，即使有符号类型是符号数值或补码

当然，如果你想输入更多内容，也可以将其转换为有符号类型

x = -(int32_t)x;

。你还有另一个解决方案

x = ~x + 1; // by 2's complement definition

---

一个易于理解的解决方案

while (!(x & 0x80000000))
    x |= x << 1;

此代码不需要像上面的许多解决方案那样始终不断循环 32 次

Answer 4

uint32_t f(uint32_t x)
{
  bool bitset=false; //C++
  for (int i =0; i<sizeof(int); i++) {
     if(bitset) //After the first 1
        {  x |= 1 << i; } 
      else
        {
          if(x&(1<<i))
            bitset=true; //if 1 found then the flag is raised
        }

  }
  return x;
}

Answer 5

不确定这个答案有多相关，但这些操作很幸运......

(!!n << 31) >> (n + ~0);

最左边的位设置为 1，最右边的位设置为 0，仅取决于 n，假设为 32 位。 我认为也可以逐行移动以获得所需的结果......

'int x=1;'
'x=x|(x<<4);'
'x=x|(x<<8);'
'x=x|(x<<16);'
'return x;'