代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
这是一个可移植的模块(ANSI-C),它可以在任何架构上对每个算法进行基准测试。
你的CPU有9位字节?目前它实现了2个算法,K&R算法和一个字节查找表。查找表的平均速度比K&R算法快3倍。如果有人能想出办法使“黑客的喜悦”算法可移植,请随意添加它。
#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
其他回答
如果您恰好使用Java,则内置方法Integer。bitCount会这样做。
我总是在竞争性编程中使用它,它很容易写,而且效率很高:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
我使用下面的函数。我还没有检查基准测试,但它是有效的。
int msb(int num)
{
int m = 0;
for (int i = 16; i > 0; i = i>>1)
{
// debug(i, num, m);
if(num>>i)
{
m += i;
num>>=i;
}
}
return m;
}
对于232查找表和逐个遍历每个位之间的折中方法:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
从http://ctips.pbwiki.com/CountBits
我认为最快的方法——不使用查找表和popcount——是以下方法。它仅通过12次操作来计数设置位。
int popcount(int v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
它之所以有效,是因为你可以通过将设置位分为两半来计算总设置位的数量,计算两半设置位的数量,然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。
v = v - ((v >> 1) & 0x55555555);
两位位数可以是0b00、0b01或0b10。让我们试着在2位上解决这个问题。
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
这就是所需要的:最后一列显示每两个位对中设置位的计数。如果两个比特数>= 2 (0b10),则产生0b01,否则产生0b00。
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
这句话应该很容易理解。在第一个操作之后,我们每两个比特中就有一个set位的计数,现在我们每4个比特中就有一个set位的计数。
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
然后我们把上面的结果加起来,得到4位的集合位总数。最后一个陈述是最棘手的。
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
让我们进一步分析一下……
v + (v >> 4)
这和第二种说法很相似;我们以4为一组来计数集合位。因为我们之前的运算,我们知道每一个咬痕都有一个集合位的计数。让我们看一个例子。假设我们有字节0b01000010。这意味着第一个啃食有它的4位设置,第二个有它的2位设置。现在我们把这些小块加在一起。
v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100
它为我们提供了一个字节中set位的计数,在第二个nibble 0b01000110中,因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。
0b01000110 & 0x0F = 0b00000110
现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010,它有一个有趣的属性。如果我们的数字有四个字节,A B C D,它将产生一个新的数字,包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位,可以表示为0b00100000。
我们现在需要的是第一个字节,它是所有字节中所有set位的和,我们通过>> 24得到它。该算法是为32位字设计的,但可以很容易地修改为64位字。