Java Integer.highestOneBit 在 C# 中

Question

我一直在努力寻找 C# 中 Java 的 Integer.highestOneBit(int) 的确切替代品。

我什至试图找到它的源代码，但无济于事。

Java文档告诉这个函数：

Returns an int value with at most a single one-bit, in the position of the highest-order ("leftmost") one-bit in the specified int value.

那么我将如何在 C# 中实现它？任何帮助或 link/redirection 表示赞赏。

Answer 1

This site 提供了一个应该在 C# 中工作的实现，只需进行一些修改：

public static uint highestOneBit(uint i) 
{
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >>  16);
    return i - (i >> 1);
}

http://ideone.com/oEiNcM

基本上就是把比最高位低的所有位都补上1，然后除掉最高位。

示例（仅使用 16 位而不是 32 位）：

start: i =        0010000000000000
i |= (i >> 1)     0010000000000000 | 0001000000000000 -> 0011000000000000
i |= (i >> 2)     0011000000000000 | 0000110000000000 -> 0011110000000000
i |= (i >> 4)     0011110000000000 | 0000001111000000 -> 0011111111000000
i |= (i >> 8)     0011111111000000 | 0000000000111111 -> 0011111111111111
i - (i >> 1)      0011111111111111 - 0001111111111111 -> 0010000000000000

Answer 2

您可以为 int 类型编写自己的扩展方法：

public static class Extensions
{
    public static int HighestOneBit(this int number)
    {
        return (int)Math.Pow(2, Convert.ToString(number, 2).Length - 1);
    }
}

所以它可以用作

int number = 170;
int result = number.HighestOneBit(); //128

或直接

int result = 170.HighestOneBit(); //128

工作原理如下：

ToString(number, 2) 以二进制形式写入我们的数字（例如：10101010 表示 170）。然后我们使用第一位位置（长度 - 1）来计算 2^(first bit position) 的值，在本例中为 128。最后，由于 Math.Pow returns a double，我们向下转换为 int.

Answer 3

更新： .NET Core 3.0 引入了 BitOperations.LeadingZeroCount() and BitOperations.Log2() 直接映射到底层 CPU 的按位前导零计数指令，因此非常高效

public static uint highestOneBit(uint i) 
{
    return i == 0 ? 0 : 1 << BitOperations.Log2(i); // or
    // return i == 0 ? 0 : 1 << (31 - BitOperations.LeadingZeroCount(i));
}

这基本上是 向下到 2 的下一个幂，在著名的 bithacks 站点。 四舍五入向上到 2 的下一个幂的实现，所以只需向右移动 1 即可得到你想要的

public static uint highestOneBit(uint i) 
{
   v--;
   v |= v >> 1;
   v |= v >> 2;
   v |= v >> 4;
   v |= v >> 8;
   v |= v >> 16;
   v++;      // now v is the next power of 2
   v >>= 1;  // get the previous power of 2
}

Another way:

public static uint highestOneBit(uint v) 
{
   const int MultiplyDeBruijnBitPosition[32] = 
   {
      0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
      8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
   };

   v |= v >> 1;
   v |= v >> 2;
   v |= v >> 4;
   v |= v >> 8;
   v |= v >> 16;

   return 1 << MultiplyDeBruijnBitPosition[(v*0x07C4ACDDU) >> 27];
}

Java Integer.highestOneBit 在 C# 中

Java Integer.highestOneBit in C#

c#

bit-manipulation