in reply to reliable get position of leftmost bit in large integers

This is very efficient in C. It works in Perl, but you'll have to time it and compare it against the other methods:

#! perl -slw
use strict;

sub nextPowerOfTwo {
    use integer;
    my $v = shift;
    $v--;
    $v |= $v >> 1;
    $v |= $v >> 2;
    $v |= $v >> 4;
    $v |= $v >> 8;
    $v |= $v >> 16;
    return ++$v;
}

print "$_ : ", nextPowerOfTwo( $_- 1 ) for map 1 << $_, 0 .. 63;

__END__
C:\test>nextPowerOfTwo.pl
1 : 0
2 : 1
4 : 4
8 : 8
16 : 16
32 : 32
64 : 64
128 : 128
256 : 256
512 : 512
1024 : 1024
2048 : 2048
4096 : 4096
8192 : 8192
16384 : 16384
32768 : 32768
65536 : 65536
131072 : 131072
262144 : 262144
524288 : 524288
1048576 : 1048576
2097152 : 2097152
4194304 : 4194304
8388608 : 8388608
16777216 : 16777216
33554432 : 33554432
67108864 : 67108864
134217728 : 134217728
268435456 : 268435456
536870912 : 536870912
1073741824 : 1073741824
2147483648 : 2147483648
4294967296 : 4294967296
8589934592 : 8589934592
17179869184 : 17179869184
34359738368 : 34359738368
68719476736 : 68719476736
137438953472 : 137438953472
274877906944 : 274877906944
549755813888 : 549755813888
1099511627776 : 1099511627776
2199023255552 : 2199023255552
4398046511104 : 4398046511104
8796093022208 : 8796093022208
17592186044416 : 17592186044416
35184372088832 : 35184372088832
70368744177664 : 70368744177664
140737488355328 : 140737488355328
281474976710656 : 281474976710656
562949953421312 : 562949953421312
1125899906842624 : 1125899906842624
2251799813685248 : 2251799813685248
4503599627370496 : 4503599627370496
9007199254740992 : 9007199254740992
18014398509481984 : 18014398509481984
36028797018963968 : 36028797018963968
72057594037927936 : 72057594037927936
144115188075855872 : 144115188075855872
288230376151711744 : 288230376151711744
576460752303423488 : 576460752303423488
1152921504606846976 : 1152921504606846976
2305843009213693952 : 2305843009213693952
4611686018427387904 : 4611686018427387904
9223372036854775808 : 9223372036854775808

[download]
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Replies are listed 'Best First'.
Re^2: reliable get position of leftmost bit in large integers
by wollmers (Scribe) on Mar 12, 2015 at 12:38 UTC

    Works perfect. I only changed the testing-lines for better visability:

    for (map 1 << $_, 0 .. 63) {
  print sprintf("%b", $_- 1 )," : ", sprintf("%b",nextPowerOfTwo( $_- 
+1 ));
}

$ perl leftmost_bit.pl 
0 : 0
1 : 1
11 : 100
111 : 1000
1111 : 10000
...

    [download]

    Maybe it's fast enough versus log(),division,log() if inlined. But I am only prototyping the pure Perl version for a C implementation. But it would be nice to have pure Perl as a fallback.

[reply]
[d/l]
      I am only prototyping the pure Perl version for a C implementation.

      If your doing it in C, it is very efficient compared to other methods; and works well as an Inline::C routine.

      It originates from Bit Twiddling Hacks.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

        I knew the Bit Twiddling page. But I hoped to get it shorter.

        Sure, pure C does not have the overhead.

        Helmut Wollmersdorfer

[reply]

In Section Seekers of Perl Wisdom