These are the slides from a tech talk I gave at NWERC (a programming competition).
The example in the background was from Hacker's Delight:
unsigned snoob(unsigned x) {
unsigned smallest, ripple, ones;
// x = xxx0 1111 0000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x ^ ripple; // 0001 1111 0000
ones = (ones >> 2)/smallest; // 0000 0000 0111
return ripple | ones; // xxx1 0000 0111
}
Given a subset (represented as a bit map), it finds the lexicographically next subset with the same number of elements. Equivalently, it finds the next integer with the same number of one-bits. Work it out, it's nice.
erling@medallia.com
Foo Bar Baz 1 2 3 1 4 1 2 4 3 5 3 2 3 5 6
(foo == 1) && (bar == 2)
Foo Bar Baz
1 2 3
1 4 1
2 4 3
5 3 2
3 5 6
--------------
struct rec {
byte foo,bar,baz;
};
rec *data;
for(o on data) {
if(o->foo == 1 &&
o->bar == 2) {
...
}
}
Foo Bar Baz 1 2 3 1 4 1 2 4 3 5 3 2 3 5 6 -------------- foo: [ 1, 1, 2, 5, .. ] bar: [ 2, 4, 4, 3, .. ] baz: [ 3, 1, 3, 2, .. ]
Foo Bar Baz
1 2 3
1 4 1
2 4 3
5 3 2
3 5 6
--------------
foo[0] = 0x11253....
bar[0] = 0x24435....
for(i) {
a = awords[i];
b = bwords[i];
for(ofs : [0,4,8..]) {
if((a>>ofs) & 0xf == 1 &&
(b>>ofs) & 0xf == 2) {
}
}
}
for(i) {
a = awords[i];
b = bwords[i];
if((a>> 0) & 0xf == 1 && (b>>0) & 0xf == 2) ...
if((a>> 4) & 0xf == 1 && (b>>4) & 0xf == 2) ...
if((a>> 8) & 0xf == 1 && (b>>8) & 0xf == 2) ...
}
0101 1100 1001 0101 ....
0101 1100 1001 0101 values
xor
0101 0101 0101 0101 search key
equals
0000 1001 1100 0000 wrong bits
0101 1100 1001 0101 values
xor
1010 1010 1010 1010 NOT search key
equals
1111 0110 0011 1111 matching bits
---- ----
1111 0110 0011 1111
x = x & (x>>1);
0111 0010 0001 1111
x = x & (x>>2);
0001 0000 0000 0011
x = x & 0x11111...;
0001 0000 0000 0001
3 2 1 0 0000 0001 0000 0000 // locate the 1 bits
// java.lang.Integer:
public static int numberOfTrailingZeros(int i) {
int y;
if (i == 0) return 32;
int n = 31;
y = i <<16; if (y != 0) { n = n -16; i = y; }
y = i << 8; if (y != 0) { n = n - 8; i = y; }
y = i << 4; if (y != 0) { n = n - 4; i = y; }
y = i << 2; if (y != 0) { n = n - 2; i = y; }
return n - ((i << 1) >>> 31);
}
000011010100110000 X
111100101011001111 ~ X
111100101011010000 (~ X) + 1
111100101011010000 -X
000000000000010000 X & -X
0x01234567 *
0x00000100 =
0x23456700
0x23456700 >> 28 == 2
while(x != 0) {
int bit = x&-x;
matched( ofs*8 + ((bit*0x01234567) >>> 28));
x -= bit;
}
before:
x[0] = 0001 0111 0101 0111 1001 ....
x[1] = ....
after:
x[0] = 000011.
x[1] = 011100.
x[2] = 010101.
x[3] = 111111.
for(ofs) {
int matches = x[ofs] & ~x[ofs+1] & x[ofs+2] & ~x[ofs+3]
& ~y[ofs] & y[ofs+1] & ~y[ofs+2] & y[ofs+3];
while(matches != 0) {
matched( ofs*32 + numberOfTrailingZeros(v) );
matches &= v-1;
}
}
int evilBitPos(x) {
int bit = x & -x;
return table[ (bit * 2510000032) >>> 27 ];
}
10010101100110111000111110100000
(000) 10010101100110111000111110100000
--- -- ----- -----
all 5-bit substrings are different
10 ms