Bits of integer

[John Keith]

(12-05-2022 10:06 PM)robve Wrote:  For C (and lua etc) I came up with a simple binary search to find the position of the leading bit in a 32 bit integer in 5 search steps:

Code:

  unsigned int n, k, v = <number>;
  k = -!!(v >> 16) & 16;
  n = k;
  v >>= k;
  k = -!!(v >> 8) & 8;
  n += k;
  v >>= k;
  k = -!!(v >> 4) & 4;
  n += k;
  v >>= k;
  k = -!!(v >> 2) & 2;
  n += k;
  v >>= k;
  k = -!!(v >> 1) & 1;
  n += k;
  v >>= k;

This is similar to Joe Horn's program from 1-Minute Marvels:

Code:


\<< 0 1 ROT
  FOR c 1 + c
  STEP
\>>

which is especially nice for the 49 and 50 since it is accurate for integers of any size.