计算 Int32 中的前导零 [英] Count leading zeroes in an Int32

问题描述

如何计算 Int32 中的前导零?所以我想要做的是编写一个函数，如果我的输入是 2，它会返回 30，因为在二进制中我有 000...0000000000010.

How do I count the leading zeroes in an Int32? So what I want to do is write a function which returns 30 if my input is 2, because in binary I have 000...0000000000010.

推荐答案

注意 使用 dotnet core >=3.0?看看这里.

NOTE Using dotnet core >=3.0? Look here.

我们以数字 20 为例.它可以用二进制表示如下:

Let's take the number 20 as an example. It can be stated in binary as follows:

    00000000000000000000000000010100

首先我们涂抹"通过右移和按位或运算在较低位位置上的最高有效位.

First we "smear" the most significant bit over the lower bit positions by right shifting and bitwise-ORing over itself.

    00000000000000000000000000010100
 or 00000000000000000000000000001010 (right-shifted by 1)
 is 00000000000000000000000000011110

然后

    00000000000000000000000000011110
 or 00000000000000000000000000000111 (right-shifted by 2)
 is 00000000000000000000000000011111

这里，因为它是一个小数，我们已经完成了工作，但是通过继续进行 4、8 和 16 位移位的过程，我们可以确保对于任何 32 位数字，我们已经设置了所有0 到原数的 MSB 到 1 的位.

Here, because it's a small number, we've already completed the job, but by continuing the process with shifts of 4, 8 and 16 bits, we can ensure that for any 32-bit number, we have set all of the bits from 0 to the MSB of the original number to 1.

现在，如果我们计算smeared"中 1 的数量.结果，我们可以简单地从 32 中减去它，我们得到原始值中前导零的数量.

Now, if we count the number of 1s in our "smeared" result, we can simply subtract it from 32, and we are left with the number of leading zeros in the original value.

我们如何计算整数中设置的位数?这个页面有一个神奇的算法来做到这一点(";一种用于执行树简化的可变精度 SWAR 算法……如果你明白了，你比我聪明！)，转换为 C# 如下:

How do we count the number of set bits in an integer? This page has a magical algorithm for doing just that ("a variable-precision SWAR algorithm to perform a tree reduction"... if you get it, you're cleverer than me!), which translates to C# as follows:

int PopulationCount(int x)
{
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return (x & 0x0000003f);
}

通过使用我们的smearing"内联这个方法上面的方法，我们可以产生一种非常快速、无循环和无条件的方法来计算整数的前导零.

By inlining this method with our "smearing" method above, we can produce a very fast, loop-free and conditional-free method for counting the leading zeros of an integer.

int LeadingZeros(int x)
{
    const int numIntBits = sizeof(int) * 8; //compile time constant
    //do the smearing
    x |= x >> 1; 
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    //count the ones
    x -= x >> 1 & 0x55555555;
    x = (x >> 2 & 0x33333333) + (x & 0x33333333);
    x = (x >> 4) + x & 0x0f0f0f0f;
    x += x >> 8;
    x += x >> 16;
    return numIntBits - (x & 0x0000003f); //subtract # of 1s from 32
}

这篇关于计算 Int32 中的前导零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！