计算整数中设置的位数 [英] Counting number of bits set in an integer

问题描述

由查找表设置的计数位

Counting bits set by lookup table

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] +	
    BitsSetTable256[p[3]];


// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

谁能解释一下这段代码的工作原理，请告诉我如何创建查找表.

Can anyone explain me how this code works and please tell me how to create look up table .

推荐答案

让我们一步一步地进行:
首先是这段代码(希望您知道宏的工作原理):

lets go through step by step:
first this code, (I hope you know how macro works):

static const unsigned char BitsSetTable256[256] = 

{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
}; //this above code define the lookup table from 0 to 255 for each value how many bit is used. hell of genius work. I wish I have half the brain 

//its not possible to go through all the conversion but i will show only B6(0)
//B6(0) will create the below code
B4(0),B4(0+1), B4(0+1), b4(0+2)
//the above macro will converted to below macor
B2(0), B2(0), B2(0+1), B2(0+2)//i am showing only B4(0)
//then the above will be transferred to 
0, 0+1, 0+1, 0+2 //here you go getting 256 numeric value

第二种选择

second option

// Option 1:
c = BitsSetTable256[v & 0xff] +  //if you do and operation with any_value and 0xff, it will set to first 24 bit to zero and keep last 8 bit unchanged  
    BitsSetTable256[(v >> 8) & 0xff] + //it will right shift 8 bit and the and operation will make first 24 bit zero, first 8 bit is already zero 
    BitsSetTable256[(v >> 16) & 0xff] + //it will right shift 16 bit and the and operation will make first 24 bit zero, first 16 bit is already zero 
    BitsSetTable256[v >> 24]; //it will right shift 24 bit and the and operation will make first 24 bit zero, first 24 bit is already zero

在上面的索引中，您永远不会获得超过255的值，因此不必担心验证其工作原理，请检查编译器中的代码

in above indexing you will never get value more than 255, so no worry to verify how it work check the code in your compier

unsigned int a=2863311530; //in binary its a combination of 10 16 times
unsigned int b;
b=a & 0xff;
b=a>>8 & 0xff;
b=a>>16 & 0xff;
b=a>>24 & 0xff;

现在检查以下定义:

now check the definition below:

//this is the power and weakness(for programmer) for c/c++ 
unsigned char * p = (unsigned char *) &v;
//when you define above you can access all 4 bytes of v as each 1 byte value in p[0], p[1], p[2], p[3]

再次使用您的编译器并测试以下代码:

take your compiler again and test the below code:

unsigned int a=1684234849;
unsigned char *b=(unsigned char*)&a;

//now if you verify the value of b you will see: b[0]='a', b[1]='b', b[2]='c', b[3]='d', rest is garbage value

希望您能借助上面的示例理解下面的代码，因为您知道每个字节可以容纳0-255个值.

I hope you would understand how the below code work with the help of above example, cause you know each byte can hold between 0-255 values

c = BitsSetTable256[p[0]] + //in the look up table the count for bit is already assigned. so from 0 to 255 whatever value you pass you will get the bit count
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] +	
    BitsSetTable256[p[3]];

我也相信您会理解其余的代码.

我给了你代码的解释.

I also believe you will understand the rest of the code.

I gave you the explanation of the code.

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