Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Bitwise OR?

Reply
Thread Tools

Bitwise OR?

 
 
xkenneth
Guest
Posts: n/a
 
      03-24-2006
Why is 3500 | -67 equal to 3500 instead of -3567?

 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      03-24-2006
xkenneth schrieb:
> Why is 3500 | -67 equal to 3500 instead of -3567?


It isn't - its -67.

Diez


 
Reply With Quote
 
 
 
 
Tim N. van der Leeuw
Guest
Posts: n/a
 
      03-24-2006

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

 
Reply With Quote
 
Tim N. van der Leeuw
Guest
Posts: n/a
 
      03-24-2006
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

 
Reply With Quote
 
Clemens Hepper
Guest
Posts: n/a
 
      03-24-2006
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
 
Reply With Quote
 
Clemens Hepper
Guest
Posts: n/a
 
      03-24-2006
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
 
Reply With Quote
 
Tim N. van der Leeuw
Guest
Posts: n/a
 
      03-24-2006
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

 
Reply With Quote
 
Diez B. Roggisch
Guest
Posts: n/a
 
      03-24-2006
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
 
Reply With Quote
 
Adam DePrince
Guest
Posts: n/a
 
      03-24-2006
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

 
Reply With Quote
 
Clemens Hepper
Guest
Posts: n/a
 
      03-26-2006
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
BitWise Operations =?Utf-8?B?Sm9u?= ASP .Net 3 01-24-2006 09:19 AM
bitwise comparator Random ASP .Net 2 06-08-2005 05:28 PM
Re: Odd Perl bitwise-AND & MySQL problem? dohnut Perl 0 10-21-2003 03:55 AM
Re: Odd Perl bitwise-AND & MySQL problem? dohnut Perl 1 10-21-2003 03:46 AM
Odd Perl bitwise-AND & MySQL problem? dohnut Perl 0 10-20-2003 09:26 PM



Advertisments