C# 从第一个有效位开始获取 uint32 的高 4 位

Question

我的需要是 - 有一些（实际上是伪的）随机数 uint32，我需要它的前 4 位用第 1 位表示，而不是 0，例如

...000100101 => 1001

1000...0001 => 1000

...0001 => 0001

...0000 => 0000

等我知道我必须使用这样的东西

uint num = 1157 (some random number)
uint high = num >> offset

问题是 - 我不知道第一位在哪里，所以我不能将 >> 与常量一起使用。谁能解释一下如何找到这个 offset?

Answer 1

您可以先计算出最高有效位（HSB），然后进行相应的移位。你可以这样：

int hsb = -4;
for(uint cnum = num; cnum != 0; cnum >>= 1, hsb++);
if(hsb < 0) {
    hsb = 0;
}
uint result = num >> hsb;

因此我们首先旨在检测最高设置位的索引（或该索引减去四）。我们通过递增 hsb 并将 cnum（num 的副本）向右移动，直到 cnum.

中不再有设置位为止

接下来我们确保有这样的设置位并且它至少有索引四（如果没有，那么什么都不做）。结果是原来的 num 向右移动 hsb.

如果我运行在 0x123 上执行此操作，我会在 csharp 交互式 shell:

中得到 0x9

csharp> uint num = 0x123;
csharp> int hsb = -4;
csharp> for(uint cnum = num; cnum != 0; cnum >>= 1, hsb++);
csharp> if(hsb < 0) {
      >     hsb = 0;
      > }
csharp> uint result = num >> hsb;
csharp> result
9

0x123 在二进制中是 0001 0010 0011。所以：

000<b>1 001</b>0 0011
   1 001

而1001是9。

Answer 2

确定最高有效非零位的位置与计算以 2 为底的对数相同。"bit shift tricks" 可以在现代 CPU 上快速完成此操作：

int GetLog2Plus1(uint value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    value -= value >> 1 & 0x55555555;
    value = (value >> 2 & 0x33333333) + (value & 0x33333333);
    value = (value >> 4) + value & 0x0F0F0F0F;
    value += value >> 8;
    value += value >> 16;
    value &= 0x0000003F;
    return (int) value;
}

这将 return 一个从 0 到 32 的数字：

Value                                      | Log2 + 1
-------------------------------------------+---------
0b0000_0000_0000_0000_0000_0000_0000_0000U |        0
0b0000_0000_0000_0000_0000_0000_0000_0001U |        1
0b0000_0000_0000_0000_0000_0000_0000_0010U |        2
0b0000_0000_0000_0000_0000_0000_0000_0011U |        2
0b0000_0000_0000_0000_0000_0000_0000_0100U |        3
...
0b0111_1111_1111_1111_1111_1111_1111_1111U |       31
0b1000_0000_0000_0000_0000_0000_0000_0000U |       32
0b1000_0000_0000_0000_0000_0000_0000_0001U |       32
...                                        |
0b1111_1111_1111_1111_1111_1111_1111_1111U |       32

（数学挑剔者会注意到 0 的对数是未定义的。但是，我希望上面的 table 演示了如何处理它并且对这个问题有意义。）

如果值小于 8（其中 log2 + 1 < 4），考虑到您需要 4 个最低有效位，然后您可以计算最高有效非零位：

var log2Plus1 = GetLog2Plus1(value);
var bitsToShift = Math.Max(log2Plus1 - 4, 0);
var upper4Bits = value >> bitsToShift;

C# 从第一个有效位开始获取 uint32 的高 4 位

C# getting upper 4 bits of uint32 starting with first significant bit

c#

bit-manipulation

uint32