6 가지 바 이 너 리 중 1 을 구 하 는 알고리즘 자바 구현

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 {

	@Override
	public int normal(int x) {
		int c = 0;
		for (; x > 0; x >>>= 1) {
			c += x & 1; //        1，     1
		}
		return c;
	}

	@Override
	public int quick(int x) {
		int c = 0;
		for (; x > 0; c++) {
			x &= (x - 1); //        1
		}
		return c;
	}

	@Override
	public 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;
	}

	@Override
	public 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;
	}

	@Override
	public int parallel(int x) {
		// 0x55 = 0101 0101
		x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);
		//0x33 = 0011 0011
		x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
		//0x0f = 0000 1111
		x = (x & 0x0f0f0f0f) + ((x >>> 4) & 0x0f0f0f0f);
		//0x00ff = 0000 0000 1111 1111
		x = (x & 0x00ff00ff) + ((x >>> 8) & 0x00ff00ff);
		//0x0000ffff = 0000 0000 0000 0000 1111 1111 1111 1111
		x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);
		
		return x;
	}

	@Override
	public 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;

	@Test
	public final void testNormal() {
		assert(bcm.normal(x) == 6);
	}

	@Test
	public final void testQuick() {
		assert(bcm.quick(x) == 6);
	}

	@Test
	public final void testStatic4bit() {
		assert(bcm.static4bit(x) == 6);
	}

	@Test
	public final void testStatic8bit() {
		assert(bcm.static8bit(x) == 6);
	}

	@Test
	public final void testParallel() {
		assert(bcm.parallel(x) == 6);
	}

	@Test
	public final void testPerfectness() {
		assert(bcm.perfectness(x) == 6);
	}

}