Bit twiddling

Luke Gorrie luke@REDACTED
Thu Mar 31 20:04:32 CEST 2005

"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!


Hacker's Delight

Count number of On bits in an integer

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, ?INTEGER_EXT, 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,
          <<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/big-unsigned-integer, 0,
           Ds:S/binary>> ->
              K = S - 1,
              <<_:K/binary, Top>> = Ds,
  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 :-)

More information about the erlang-questions mailing list