Question: Count the number of set bits in an 32 integer.
Method 1:
Count the bit one by one, 这显然不好:
public int bitCount(int a) { int num = 0; for (int i=0; i<32; ++i) { if ((a & (1<<i)) != 0) num++; } return num; }
Method 2:
仅查被set的位。
public int bitCount(int n) { int count = 0; while(n != 0){ count++; n &= n-1; } return count; }
Method 3:
注意Java里面要用>>>,代表把符号一块儿右移。
public int bitCount(int a) { a = ((0xAAAAAAAA & a)>>>1) + (0x55555555 & a); a = ((0xCCCCCCCC & a)>>>2) + (0x33333333 & a); a = ((0xF0F0F0F0 & a)>>>4) + (0x0F0F0F0F & a); a = ((0xFF00FF00 & a)>>>8) + (0x00FF00FF & a); a = ((0xFFFF0000 & a)>>>16) + (0x0000FFFF & a); return a; }
Method 4:
上面的方法还可以改进为下面这样,方便好记。
public int bitCount(int n) { n = (n & 0x55555555) + ((n>>>1) & 0x55555555); n = (n & 0x33333333) + ((n>>>2) & 0x33333333); n = (n & 0x0F0F0F0F) + ((n>>>4) & 0x0F0F0F0F); n = (n & 0x00FF00FF) + ((n>>>8) & 0x00FF00FF); n = (n & 0x0000FFFF) + ((n>>>16) & 0x0000FFFF); return n; }
Method 5:
Hacker's Delight里的方法,也是Java源码的实现方法。
public int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }
相关推荐
How to count the number of lines in a text file
Count the number of bits set in an unsigned number Chapter 9. Add two numbers without using arithmetic operators Chapter 10. Given an array of integers where all the numbers are appearing twice find ...
labview labview_labview示例之Count the Number
numbers, and they have an equally complex and intriguing history, from Euclid's famous proof that the square root of 2 is irrational to Roger Apéry's proof of the irrationality of a number called ...
count the number of set hits for this segment.
Count the frequency distribution of units digits
This time, you are supposed to find A+B where A and B are two matrices, and then count the number of zero rows and columns.
count the number of digits to be copied for Linux v2.13.6.
A Method for Vehicle Count in the Presence of Multiple-Vehicle Occlusions in Traffic Images
Given two integers n and m, count the number of pairs of integers (a,b) such that 0 (a^2+b^2 +m)/(ab) is an integer. This problem contains multiple test cases! The first line of a multiple input is an...
shell script file to count the number of girls who have filled the questionnaire
Program Description: The program asks the user to choice from the menu an option A. Check to see if a number is prime.... Count the number of vowels in a line. X. Exit the program.
Count the number of attributes specified by the application. All attributes appear in pairs, except the terminating None.
python实现: 二进制和运算符 二进制计数设置位 二进制计数尾随零 二进制或运算符 二进制移位 二进制二进制补码 二进制异或运算符 ... Count Number Of One Bits Gray Code Sequence Highest Set Bit
The number of levels in an index will vary depending on the number of rows in the table and the size of the key column or columns for the index. If you create an index using a large key, fewer ...
2.count Frequency of number.exe
Add an environment variable. Count the number of existing ones, and then allocate up a new vector of environment strings and add ours to it.
为一个字符串或者一段字符串(包括多个字符串)定义一个类Word,这个类至少包含2个成员变量,1是这个字符串(用指向动态数组的指针表示),2是字符串中单词的个数(若还需要其他成员变量,自己定义)。
The boot.ini option /3GB was created for those cases where systems actually support greater than 2 GB of physical memory and an application can make use of it This capability allows memory intensive ...
report on your favorite book