Bit counting

bitcount.java

	public static int countBits1(long x) {
		int c = 0;
		long v = x;
		while (v!=0) {
			v &= v - 1;
			c++;
		}
		return c;
	}

	private static int countBits2(long x) {
		// collapsing partial parallel sums method
		// collapse 64x1 bit counts to 32x2 bit counts, mask 01010101
		x = (x >>> 1 & 0x5555555555555555L) + (x & 0x5555555555555555L);
		// collapse 32x2 bit counts to 16x4 bit counts, mask 00110011
		x = (x >>> 2 & 0x3333333333333333L) + (x & 0x3333333333333333L);
		// collapse 16x4 bit counts to 8x8 bit counts, mask 00001111
		x = (x >>> 4 & 0x0f0f0f0f0f0f0f0fL) + (x & 0x0f0f0f0f0f0f0f0fL);
		// collapse 8x8 bit counts to 4x16 bit counts
		x = (x >>> 8 & 0x00ff00ff00ff00ffL) + (x & 0x00ff00ff00ff00ffL);
		// collapse 4x16 bit counts to 2x32 bit counts
		x = (x >>> 16 & 0x0000ffff0000ffffL) + (x & 0x0000ffff0000ffffL);
		// collapse 2x32 bit counts to 1x64 bit count
		return (int)((x >>> 32) + (x & 0xffffffff));
	}

	private static int pop2(long x, long y)
	{
	    x = x - ((x >>> 1) & 0x5555555555555555L);
	    y = y - ((y >>> 1) & 0x5555555555555555L);
	    x = (x & 0x3333333333333333L) + ((x >>> 2) & 0x3333333333333333L);
	    y = (y & 0x3333333333333333L) + ((y >>> 2) & 0x3333333333333333L);
	    x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
	    y = (y + (y >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
	    x = x + y; 
	    x = x + (x >>> 8);
	    x = x + (x >>> 16);
	    x = x + (x >>> 32); 
	    return (int)(x & 0xFF);
	}