Bits of integer

[robve]

Here is a cryptic "one liner" in C for binary search with left shifts and a right shift by one bit (for division by two):

unsigned int k, n, u, v, w = <number>; for (k = 16, n = 0, v = 1, u = v << k; k; k >>= 1, u = v << k) if (w >= u) { n += k; v = u; }

or how about the same with multiplications and square roots, in case shifts aren't permitted:

unsigned int k, n, s, u, v, w = <number>; for (k = 16, n = 0, v = 1, u = s = 65536; k; k /= 2, s = sqrt(s), u = v * s) if (w >= u) { n += k; v = u; }

The square roots are simply 65536, 256, 16, 4, 2, so can be precomputed or put in an unrolled loop:

n = 0;
v = 1;
u = 65536;
if (w >= u) { n = 16; v = u; }
u = v * 256;
if (w >= u) { n += 8; v = u; }
u = v * 16;
if (w >= u) { n += 4; v = u; }
u = v * 4;
if (w >= u) { n += 2; v = u; }
u = v * 2;
if (w >= u) { n += 1; }

Add a step to extend to 64 bit numbers or a few more steps to go very far beyond if your machine can handle it.

- Rob