3

假设一个 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，我觉得有一种更聪明的方法可以做到这一点。

4

4 回答 4

5

从概念上讲，一个简单的事情是先取x-1然后用0xffffffff. 像 harold 在下面的评论中所做的那样编写它~(x-1)可以处理不同大小的整数，而无需更改您正在使用的 XORing。

于 2012-09-13T17:29:29.353 回答
2

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

于 2012-09-13T17:40:34.380 回答
0 
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;
}
于 2012-09-13T17:33:11.573 回答
0

你只需要取两个的补码

x = -x;

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

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

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

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

您只有一位 set，因此当您复制所有零位并反转剩余的零位时，您会得到其 2 的补码。您可以在示例中看到它：00001000 = 8, 11111000 = -8. 其他一些例子：

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

如果 x 是有符号类型，那么它很容易理解。在无符号类型的情况下，显然没有负值，因此它基于C 标准如何定义无符号操作来工作

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

这只是2 的补码的另一种定义，因为大于可以由结果类型（即在这种情况下）表示的最大值的一个是 2 N。对无符号值求反总是会在 C 中产生其二进制补码，即使有符号类型是符号幅度或一个补码UINTN_MAX + 1

当然，x = -(int32_t)x;如果您想输入更多内容，也可以将其转换为有符号类型。你还有另一个解决方案

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

一个易于理解的解决方案

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

这段代码不需要像上面的许多解决方案一样一直循环 32 次

于 2013-08-01T03:58:34.223 回答