Bit twiddling

[Luke Gorrie]

"Joel Reymont" <joelr1@REDACTED> writes:

> I'm looking to figure out the highest and lowest bit set in an integer as
> well as count the number of bits set.

If it needs to be fast then be sure to see what mathematician
assembler hackers have to say!

hackmem
  http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

Hacker's Delight
  http://www.hackersdelight.org/

Count number of On bits in an integer
  http://www-db.stanford.edu/~manku/bitcount/bitcount.html

Highest bit set is floor(log2(N)) if you figure out the floating
point, though Erlang doesn't have a log2 BIF. Tony Rogvall has a very
interesting "how many bits is this integer" function that makes the
runtime system do the real work in jungerl/lib/ssh/src/ssh_bits.erl:

  isize(N) when N > 0 ->
      case term_to_binary(N) of
          <<?VERSION_MAGIC, ?SMALL_INTEGER_EXT, X>> ->
              isize_byte(X);
          <<?VERSION_MAGIC, ?INTEGER_EXT, X3,X2,X1,X0>> ->
              isize_bytes([X3,X2,X1,X0]);
          <<?VERSION_MAGIC, ?SMALL_BIG_EXT, S:8/big-unsigned-integer, 0,
           Ds:S/binary>> ->
              K = S - 1,
              <<_:K/binary, Top>> = Ds,
              isize_byte(Top)+K*8;
          <<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/big-unsigned-integer, 0,
           Ds:S/binary>> ->
              K = S - 1,
              <<_:K/binary, Top>> = Ds,
              isize_byte(Top)+K*8
      end;
  isize(0) -> 0.

i.e. encode the number in the binary Erlang external term format and
then pull that apart to see the length header :-)