1

我已经考虑了这个问题好几个小时了，但解决方案不想来。也许有人有任何想法？

问题是：

 "Using ONLY bitwise operators, write the function that sets 
  the leftmost zero bit to one" 

Conditions - prohibited
Recursion - prohibited
Loops - prohibited
Arithmetic operations - prohibited

例子：

输入：11010010

输出：11110010

PS 输入实际上应该是无符号整数，但为简单起见，将其设为二进制，这只是细节。

4

3 回答 3

2

您可以像这样将最左边的零传播到右边：

x &= x >> 1;
x &= x >> 2;
x &= x >> 4;
// etc

在示例中，您将获得 11000000

然后如果你反转它，你会得到一个掩码，直到并包括最左边的零，在这个例子中，00111111

然后，您可以使用x ^ (x >> 1)

只需将其或输入输入即可。

放在一起：（未测试）

uint32_t y = x;
x &= x >> 1;
x &= x >> 2;
x &= x >> 4;
x &= x >> 8;
x &= x >> 16;
x = ~x;
return y | (x ^ (x >> 1));

可能有更简单的解决方案

于 2013-07-27T12:09:50.407 回答
0

一段时间后，哈罗德提出了类似的解决方案，但几乎没有改进。这是代码

unsigned long int getLastZeroPosition(unsigned long int value)
{
   unsigned long int temp = ~value;
   temp = temp | temp >> 1;
   temp = temp | temp >> 2;
   temp = temp | temp >> 4;
   temp = temp | temp >> 8;
   temp = temp | temp >> 16;
   temp = temp | temp >> (sizeof(unsigned long int) << 2);  // handles x86/x64

   temp = temp >> 1;
   temp = (~temp) & (~value);
   return temp;
}
于 2013-07-31T08:35:14.427 回答
0

我将假设我可以使用 Java 来实现。如果将问题更改为“仅使用位运算符，编写将RIGHTMOST零位设置为 1 的函数”，则可以按如下方式解决问题：

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111;
a = a | (a & (a^(a+1)))+1;
System.out.println(Integer.toBinaryString(a));

这个答案是我们需要的镜像，所以首先简单地镜像输入：

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111;
a = Integer.reverse(a);
a = Integer.reverse(a | (a & (a ^ (a + 1))) + 1);
System.out.println(Integer.toBinaryString(a));

但是，当然，使用一个 Java 内置 ( reverse)，您也有权使用另一个 ( highestOneBit)：

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111;
a = Integer.highestOneBit(~a)+a;
System.out.println(Integer.toBinaryString(a));

如果您想使用基本的按位运算符实现自己的reverse，并且可能在 c 中实现，那也是可能的：Reverse bits

于 2015-04-24T01:02:26.890 回答