by Ron Gutman
Listing One
public class BitLinear {
public static long reverse (long bits) {
long rl = 0;
for (int i = 0; i < 64; i++) {
rl = (rl << 1) + (bits & 1);
bits = bits >>> 1;
}
return rl;
}
public static int count (long bits) {
int cnt = 0;
while (bits != 0) {
cnt += bits & 1;
bits = bits >>> 1;
}
return cnt;
}
}
Listing Two
public class BitRecursive
{
// reverse leftmost n bits of V
static long reversen (long V, int n) {
if (n <= 1)
return V;
int n2 = n/2;
// reverse rightmost n/2 bits
long right = reversen( V & ((1L<<n2)-1), n2);
// reverse lefttmost n/2 bits
long left = reversen( V >>> n2, n2);
// combine in reverse order
return (right << n2) | left;
}
public static long reverse (long bits) {
return reversen (bits, 64);
}
}
Listing Three
public class BitLogN {
public static long reverse (long bits) {
// >>> fills bits on the left with 0 (no sign extension)
bits = ((bits&0x00000000ffffffffL) << 32) |
((bits&0xffffffff00000000L) >>> 32);
bits = ((bits&0x0000ffff0000ffffL) << 16) |
((bits&0xffff0000ffff0000L) >>> 16);
bits = ((bits&0x00ff00ff00ff00ffL) << 8) |
((bits&0xff00ff00ff00ff00L) >>> 8);
bits = ((bits&0x0f0f0f0f0f0f0f0fL) << 4) |
((bits&0xf0f0f0f0f0f0f0f0L) >>> 4);
bits = ((bits&0x3333333333333333L) << 2) |
((bits&0xccccccccccccccccL) >>> 2);
bits = ((bits&0x5555555555555555L) << 1) |
((bits&0xaaaaaaaaaaaaaaaaL) >>> 1);
return bits;
}
public static int count (long bits) {
bits = (bits&0x5555555555555555L) +
((bits&0xaaaaaaaaaaaaaaaaL) >>> 1);
bits = (bits&0x3333333333333333L) +
((bits&0xccccccccccccccccL) >>> 2);
bits = (bits&0x0f0f0f0f0f0f0f0fL) +
((bits&0xf0f0f0f0f0f0f0f0L) >>> 4);
bits = (bits&0x00ff00ff00ff00ffL) +
((bits&0xff00ff00ff00ff00L) >>> 8);
bits = (bits&0x0000ffff0000ffffL) +
((bits&0xffff0000ffff0000L) >>> 16);
bits = (bits&0x00000000ffffffffL) +
((bits&0xffffffff00000000L) >>> 32);
return (int) bits;
}
public static long mortonKey (int x, int y) {
/* In C++, the calls to spreadBits could be made in-line */
/* to avoid function call overhead. */
/* In C, make the function a macro (admittedly an ugly one) */
return (spreadBits(x) << 1) | spreadBits(y);
}
// For j = 1 to 31, shift bit j j positions to the left
static long spreadBits (int i) {
long bits = i;
// shift bits 16 to 31 16 bits
bits = (bits & 0x000000000000ffffL) |
((bits & 0x00000000ffff0000L) << 16);
// shift originally odd-numbered bytes 8 bits
bits = (bits & 0x000000ff000000ffL) |
((bits & 0x0000ff000000ff00L) << 8);
// shift originally odd-numbered nibbles 4 bits
bits = (bits & 0x000f000f000f000fL) |
((bits & 0x00f000f000f000f0L) << 4);
// shift originally odd-numbered bit pairs 2 bits
bits = (bits & 0x0303030303030303L) |
((bits & 0x0c0c0c0c0c0c0c0cL) << 2);
// shift originally odd-numbered bit pairs 1 bits
bits = (bits & 0x1111111111111111L) |
((bits & 0x2222222222222222L) << 1);
return bits;
}
}
Listing Four
public class BitTable {
short[] table = new short[256];
public BitTable() {
BitLinear lin = new BitLinear();
for (int i = 0; i < 256; i++) {
table[i] = (short) (lin.reverse(i) >>> 56);
}
}
public long reverse (long bits) {
long rl = 0;
rl = table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
rl = (rl << 8) | table[(int)(bits & 255)];
return rl;
}
}
Example 1:
if n equals 1, return V
set R = right most n/2 bits of V
set L = left most n/2 bits of V
R = reversen(R,n/2)
L = reversen(L,n/2)
set RL = n bit value whose left most n/2 bits
equals R and whose right most n/2 bits equals L
return RL
Example 2:
if n equals 1, return V set R = right most n/2 bits of V set L = left most n/2 bits of V return countn(L,n/2) + countn(R,n/2)
See also: