|
Re: reliable get position of leftmost bit in large integers
by martin (Friar) on Mar 12, 2015 at 13:39 UTC
|
To check whether the most significant bit positions of two unsigned integer values are equal (or both are zero), this works for me:
sub msb_pos_is_equal {
my ($x, $y) = @_;
($x ^ $y) <= ($x & $y)
}
Update: Added the words "unsigned integer" in the first paragraph. | [reply]
[d/l] |
|
|
Thanks. This smells very fast. I still need the value of the position, but only in case of a match, and only from one side. Then BrowserUK's solution should do it.
WOW, maybe we can beat the speed of Algorithm::Diff::XS in pure Perl. Still reached 80% yesterday.
Helmut Wollmersdorfer
| [reply] |
|
|
| [reply] |
Re: reliable get position of leftmost bit in large integers
by BrowserUk (Patriarch) on Mar 12, 2015 at 12:01 UTC
|
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
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.
| [reply]
[d/l] |
|
|
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
...
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.
| [reply] |
|
|
Re: reliable get position of leftmost bit in large integers
by hdb (Monsignor) on Mar 12, 2015 at 10:42 UTC
|
perl -e 'for my $i (1..63) {if(int(log(2**($i-1))/log(2)) != $i-1) {pr
+int "$i\n"}}'
which gives no output for me.
UPDATE: Apologies, I think I get it now, the leading one of 2^i - 1 should be in the same place as the leading one for 2^(i-1) which is what you are testing.
My next thought was to use length(sprintf("%b",$x)) but that does not work either:
for my $i (1..63) {
if(length(sprintf("%b",2**$i-1)) != length(sprintf("%b",2**($i-1))
+)) {
print"$i\n";
printf("%b\n",2**($i-1));
printf("%b\n",(2**$i)-1);
}
}
| [reply]
[d/l]
[select] |
|
|
$ perl -e 'print sprintf("%b",2**53-1),"\n"'
11111111111111111111111111111111111111111111111111111
$ perl -e 'print sprintf("%b",2**54-1),"\n"'
1000000000000000000000000000000000000000000000000000000
$ perl -e 'print sprintf("%b",2**(53-1)),"\n"'
10000000000000000000000000000000000000000000000000000
| [reply]
[d/l] |
|
|
| [reply] |
|
|
Re: reliable get position of leftmost bit in large integers
by thargas (Deacon) on Mar 12, 2015 at 13:02 UTC
|
You're using numeric operations, but you're asking questions about bit vectors. Wouldn't you be better off storing your bit vectors as bits with vec? Then you wouldn't have rounding errors caused by the numeric operations. Of course, if you're using them elsewhere as numbers, the conversion effort may not be worth it. | [reply] |
Re: reliable get position of leftmost bit in large integers
by AppleFritter (Vicar) on Mar 12, 2015 at 11:18 UTC
|
There's Math::Int64 on CPAN -- I've never used it, but perhaps it'll suit your needs. | [reply] |
Re: reliable get position of leftmost bit in large integers
by syphilis (Archbishop) on Mar 12, 2015 at 12:34 UTC
|
If $v1 and $v2 were expressed as 64-bit unsigned integers, I'd be tempted to investigate (untested):
sub is_same_leading_bit {
my ($v1, $v2) = (shift, shift);
my $and = 1 << 63;
for my $shift(0 .. 63) {
my $c1 = ($v1 << $shift) & $and;
my $c2 = ($v2 << $shift) & $and;
return 1 if $c1 & $c2;
return 0 if $c1 | $c2;
}
return 0; # both args are 0.
}
But I'd be writing the sub in C and accessing it via Inline::C or XS.
Cheers,
Rob
| [reply]
[d/l] |
