10/06/2008

10-06-08 - 6

Urg, somebody help me out, I can't find this with Goog :

There's a way to encode the integers in binary such that larger values always have more or equal number of bits "on" (=1) than smaller values. Eg. if X >= Y , then NumBitsOn(X) >= NumBitsOn(Y). There's a cool way to make this encoding using just a simple bit trick, but I don't remember where I saw it.

For example one possible encoding of 3 bit integers is :

0 : 000
1 : 001
2 : 010
3 : 100
4 : 011
5 : 101
6 : 110
7 : 111

Maybe my memory is wrong that I saw a bit trick for this. Certainly I recall seeing the trick for Gray Codes, but that's not quite the same thing.

No comments:

old rants