Bitwise OR?

[xkenneth]

Why is 3500 | -67 equal to 3500 instead of -3567?

[Diez B. Roggisch]

xkenneth schrieb:

Why is 3500 | -67 equal to 3500 instead of -3567?

It isn't - its -67.

Diez

[Tim N. van der Leeuw]

xkenneth wrote:

Why is 3500 | -67 equal to 3500 instead of -3567?

Well that's funny... On my computer, python says it's -67. Java also
says it's -67.

Haven't yet looked at the actual bits of both values.
What Python implementation and what machine do you have?

--Tim

[Tim N. van der Leeuw]

Actually, following up to my own reply:

3500 | 67 = 3567. So perhaps that sets your expectations for 3500 |
-67.

But try

-3500 | -67

for fun: it is -3

Bitwise or is no arithmetic and if you want to predict something about
the resulting integers, you should know something about how they are
stored.

Negative integers are stored in 2-complement format: minus 1 is all
bits set to 1. Turning bits off makes it a more negative number (as
long as you don't touch the sign-bit) and turning more bits on makes it
a smaller negative number.

Doing bitwise-OR for the positive numbers 3500 and 67 results in 3567:
proof that they don't have any overlapping bits.
Know it turns out that 3500 and -67 have only overlapping bits:
therefore the result is -67. (adding the bits from 3500 to the bits of
-67 doesn't turn on any extra bits).

Use bit operators to manipulate bits, and think of the operands as sets
of bits. Bitwise OR is the union of 2 sets of bits.
Don't think of the operands to bit operators as numbers, and don't try
to do your sums using bitwise or!

:-)

--Tim

[Clemens Hepper]

To look at the bit-structure i've implemented a little function:

def bitstring(number, digits=32):
"""lsb------>msb"""
result = ""
for a in xrange(digits):
if number & 1:
result += '1'
else:
result += '0'
number >>= 1
return result

I wonder if there is something like sizeof() for int numbers.

mfg
- eth

[Clemens Hepper]

Hello,

I've written a little (optimized) method to get a bit-string:

def bitstringneg(number, digits=32):
"""optimized for negative numbers"""
result = ""
for a in xrange(digits):
if number & 1:
result += '1'
else:
result += '0'
number >>= 1
return result

def bitstringpos(number):
"""optimized for positive numbers"""
result = ""
while number:
if number & 1:
result += '1'
else:
result += '0'
number >>= 1
return result

def bitstring(number, digits=32):
"""lsb------>msb"""
result = ""
if number < 0:
return bitstringneg(number, digits)
else:
return bitstringpos(number)

BTW: Is there something like a sizeof() method for int numbers?

mfg
- eth

[Tim N. van der Leeuw]

I wonder what causes one version to be faster for positive, and the
other faster for negative numbers? I can see that the pos-version
doesn't make as many iterations as the neg version, but it doesn't pad
the length of the result to the requested number of digits and
potentially produces more digits.

I also wonder if it wouldn't be faster to put the numbers into a list
and join the list into a string -- did you test with that?

Cheers,

--Tim

[Diez B. Roggisch]

Tim N. van der Leeuw wrote:

I also wonder if it wouldn't be faster to put the numbers into a list
and join the list into a string -- did you test with that?

It will be faster - the naive string concatenation is quadratic, whereas the
list-based approach is linear.

Diez

[Adam DePrince]

On Fri, 2006-03-24 at 12:55 +0100, Clemens Hepper wrote:

Hello,

I've written a little (optimized) method to get a bit-string:

def bitstringneg(number, digits=32):
"""optimized for negative numbers"""
result = ""
for a in xrange(digits):
if number & 1:
result += '1'
else:
result += '0'
number >>= 1
return result

def bitstringpos(number):
"""optimized for positive numbers"""
result = ""
while number:
if number & 1:
result += '1'
else:
result += '0'
number >>= 1
return result

def bitstring(number, digits=32):
"""lsb------>msb"""
result = ""
if number < 0:
return bitstringneg(number, digits)
else:
return bitstringpos(number)

BTW: Is there something like a sizeof() method for int numbers?

import struct
help( strict.calcsize )

Why one bit at a time?
If I rewrite your functions as:

_octets = {"0":"000", "1":"001","2":"010",
"3":"011", "4":"100","5":"101",
"6":"110", "7":"111", "-":"" }

_sign = {True:'-',False:''}

def bitstring1( number ):
return _sign[number<0] + ''.join( [_nibbles[d] for d in
hex( number )] ).lstrip( '0' )
_nibbles = {"0":"0000", "1":"0001", "2":"0010", "3":"0011",
"4":"0100", "5":"0101", "6":"0110", "7":"0111",
"8":"1000", "9":"1001", "a":"1010", "b":"1011",
"c":"1100", "d":"1101", "e":"1110", "f":"1111",
"-":"", "x":""}
def bitstring2( number ):
return _sign[number<0] + ''.join( [_nibbles[d] for d in
hex( number )] ).lstrip( '0' )

Now I know, my negative number sematincs are different than yours, I'll
leave fixing that as an exercise to you.
python2.4 -mtimeit -s 'from test_a import bitstring'
'bitstring(343890242);bitstring(-343890242)'
10000 loops, best of 3: 27.1 usec per loop

python2.4 -mtimeit -s 'from test_b import bitstring1'
'bitstring1(343890242);bitstring1(-343890242)'
100000 loops, best of 3: 10.9 usec per loop

python2.4 -mtimeit -s 'from test_b import bitstring2'
'bitstring2(343890242);bitstring2(-343890242)'
100000 loops, best of 3: 11.2 usec per loop
And if I use a map, well, its not a statistically significant
difference.

def bitstring_nibblemap( number ):
return _sign[number<0] + ''.join( map( _nibbles.get,
hex( number ))).lstrip( '0' )

python2.4 -mtimeit -s 'from test_b import bitstring_nibblemap'
'bitstring_nibblemap(343890242);bitstring_nibblema p(-343890242)'
100000 loops, best of 3: 10.7 usec per loop
Cheers - Adam

[Clemens Hepper]

Adam DePrince wrote:

BTW: Is there something like a sizeof() method for int numbers?
import struct
help( strict.calcsize )

Mh, that doesn't do what i want. I'd like to have something like:

def size(number):
return sizeof(number)
Why one bit at a time?
Good question...

Here my new approach based on your idea:

_digits = { 0:"0000", 1:"1000", 2:"0100", 3:"1100",
4:"0010", 5:"1010", 6:"0110", 7:"1110",
8:"0001", 9:"1001", 0xa:"0101", 0xb:"1101",
0xc:"0011", 0xd:"1011", 0xe:"0111", 0xf:"1111"}

def bitstring2(number):
"""lsb------>msb"""
rlist = list()
if number >= 0:
while number:
rlist.append( _digits[number & 0xF] )
number >>= 4
else:
while number != -1:
rlist.append( _digits[number & 0xF] )
number >>= 4

return ''.join(rlist)

This was faster for positive numbers. For negative numbers yours was
faster, but my version handles those numbers different.

Your version fails for Large numbers since hex( long ) returns
something like "0xFFFL" instead of "0xfff".
Cheers - Adam

Cheers :)
- eth

[Clemens Hepper]

Okay... pythons build-in methods are quite fast. so is hex().

with about 64 kb memory i can write it with a 16 bit dictionary
where the dictionary generation itself is not yet optimized:

def genBitList(exp):
next = lambda now: [x+'0' for x in now]+[x+'1' for x in now]
result = [""]

for x in range(exp):
result = next(result)

return result

_digits = genBitList(16)

def bitstring2(number):
"""lsb------>msb"""
rlist = list()
if number >= 0:
while number:
rlist.append( _digits[number & 0xFFFF] )
number >>= 16
return ''.join(rlist).rstrip('0')
else:
while number != -1:
rlist.append( _digits[number & 0xFFFF] )
number >>= 16
return ''.join(rlist).rstrip('1')

this is quite fast and in lots of cases faster than the
hex()-version. however your method (with my inverses formatting) is
very fast, too and without so much memory expense:

_nibbles = {"0":"0000", "1":"0001", "2":"0010", "3":"0011",
"4":"0100", "5":"0101", "6":"0110", "7":"0111",
"8":"1000", "9":"1001", "a":"1010", "b":"1011",
"c":"1100", "d":"1101", "e":"1110", "f":"1111",
"l":"", "-":"", "x":""}

from string import maketrans, translate

_invert = maketrans('01', '10')

def bitstring3( number ):
if number > 0:
return ''.join( [_nibbles[d] for d in
hex( number ).lower()] ).lstrip( '0' )
else:
return translate(''.join( [_nibbles[d] for d in
hex( ~number ).lower()] ).lstrip( '0' ), _invert)

Benchmark:
for 0xa:
bitstring2: 0.61802315712
bitstring3: 0.91001200676

for 0xaaaa:
bitstring2: 0.561501026154
bitstring3: 1.11787199974

for 0xaaaaaaaaaaaa:
bitstring2: 1.2295820713
bitstring3: 1.61559510231

for 0xaaaaaaaaaaaaaaaaaaaaaaaa:
bitstring2: 1.90036797523
bitstring3: 2.2683339119

for -0xaaaaaaaaaaaaaaaaaaaaaaaa:
bitstring2: 2.81339716911
bitstring3: 2.74266886711

mfg
- eth