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

问题描述

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

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 Int32 is 2, because in binary I have 0000000000000010.

推荐答案

我们以数字10为例。它可以二进制表示如下：

Let's take the number 10 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 00000000000000000000000000011100

然后

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

这里，因为它是一个小数字，我们已经完成了这项工作，但是通过重复这个过程直到16位的右移，我们可以确保对于任何32位数，我们将所有位从0到原始数字的MSB设置为1.

Here, because it's a small number, we've already completed the job, but by repeating the process right up to a right shift of 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.

现在，如果我们计算涂抹结果中的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);
}

通过上面的涂抹方法内联这个方法，我们可以生成一个非常快速，无循环且无条件的方法，用于计算整数的前导零。

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屋！