6 种 求二进制数中1的个数 算法 java 实现
package BitCount;/** * 任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4 * * @author vivizhyy * */public interface BitCountMethods {/** 移位+计数 */public int normal(int x);/** 不断清除x的二进制表示中最右边的1，同时累加计数器，直至x为0 */public int quick(int x);/** * @see #static8bit(int) */public int static4bit(int x);/** * 首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。 * 然后对于任意一个32bit无符号整数n * ，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位 * ，并与0xff相与，取得最低位的8bit * ，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数2882400018为例 * ，其对应的二进制数为10101011110011011110111100010010 * ，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。 * * 第一次（n & 0xff） 10101011110011011110111100010010 * * 第二次（(n >> 8) & 0xff） 00000000101010111100110111101111 * * 第三次（(n >> 16) & 0xff）00000000000000001010101111001101 * * 第四次（(n >> 24) & 0xff）00000000000000000000000010101011 */public int static8bit(int x);/** 先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。 * 1 1 0 1 1 0 0 1 * \ / \ / \ / \ / * 2 1 1 1 * \ / \ / * 3 2 * \ / * 5 */public int parallel(int x);/** http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html */public int perfectness(int x);}?
package BitCount;public class BitCounts implements BitCountMethods {@Overridepublic int normal(int x) {int c = 0;for (; x > 0; x >>>= 1) {c += x & 1; // 如果当前位是 1，计数器加 1}return c;}@Overridepublic int quick(int x) {int c = 0;for (; x > 0; c++) {x &= (x - 1); // 清除最右边的 1}return c;}@Overridepublic int static4bit(int x) {int[] table = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };int c = 0;for (; x > 0; x >>>= 4) {c += table[x & 0xF];}return c;}@Overridepublic int static8bit(int x) {int[] table = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2,2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3,4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2,3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4,4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5,6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5,5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5,4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5,6, 6, 7, 6, 7, 7, 8, };int c = 0;for(; x > 0; x >>>= 8){c += table[x & 0xFF];}return c;}@Overridepublic int parallel(int x) {// 0x55 = 0101 0101x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);//0x33 = 0011 0011x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);//0x0f = 0000 1111x = (x & 0x0f0f0f0f) + ((x >>> 4) & 0x0f0f0f0f);//0x00ff = 0000 0000 1111 1111x = (x & 0x00ff00ff) + ((x >>> 8) & 0x00ff00ff);//0x0000ffff = 0000 0000 0000 0000 1111 1111 1111 1111x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);return x;}@Overridepublic int perfectness(int x) {int temp = x - (x >>> 1) & 033333333333 - (x >>> 2) & 011111111111;return (temp +(temp >>>3)) & 030707070707 % 63;}}?
package BitCount;import static org.junit.Assert.*;import org.junit.Test;public class BitCountMethodsTest {BitCountMethods bcm = new BitCounts();int x = 123;@Testpublic final void testNormal() {assert(bcm.normal(x) == 6);}@Testpublic final void testQuick() {assert(bcm.quick(x) == 6);}@Testpublic final void testStatic4bit() {assert(bcm.static4bit(x) == 6);}@Testpublic final void testStatic8bit() {assert(bcm.static8bit(x) == 6);}@Testpublic final void testParallel() {assert(bcm.parallel(x) == 6);}@Testpublic final void testPerfectness() {assert(bcm.perfectness(x) == 6);}}??