Bitwise OR?

Discussion in 'Python' started by xkenneth, Mar 24, 2006.

  1. xkenneth

    xkenneth Guest

    Why is 3500 | -67 equal to 3500 instead of -3567?
     
    xkenneth, Mar 24, 2006
    #1
    1. Advertising

  2. xkenneth schrieb:
    > Why is 3500 | -67 equal to 3500 instead of -3567?


    It isn't - its -67.

    Diez
     
    Diez B. Roggisch, Mar 24, 2006
    #2
    1. Advertising

  3. 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, Mar 24, 2006
    #3
  4. 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
     
    Tim N. van der Leeuw, Mar 24, 2006
    #4
  5. 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, Mar 24, 2006
    #5
  6. 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
     
    Clemens Hepper, Mar 24, 2006
    #6
  7. 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
     
    Tim N. van der Leeuw, Mar 24, 2006
    #7
  8. 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
     
    Diez B. Roggisch, Mar 24, 2006
    #8
  9. 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_nibblemap(-343890242)'
    100000 loops, best of 3: 10.7 usec per loop


    Cheers - Adam
     
    Adam DePrince, Mar 24, 2006
    #9
  10. 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, Mar 27, 2006
    #10
  11. 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
     
    Clemens Hepper, Mar 27, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dohnut
    Replies:
    0
    Views:
    560
    dohnut
    Oct 20, 2003
  2. dohnut
    Replies:
    1
    Views:
    596
    Sam Holden
    Oct 21, 2003
  3. dohnut
    Replies:
    0
    Views:
    596
    dohnut
    Oct 21, 2003
  4. Random

    bitwise comparator

    Random, Jun 8, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    1,176
    Random
    Jun 8, 2005
  5. =?Utf-8?B?Sm9u?=

    BitWise Operations

    =?Utf-8?B?Sm9u?=, Jan 23, 2006, in forum: ASP .Net
    Replies:
    3
    Views:
    3,411
    =?Utf-8?B?Sm9u?=
    Jan 24, 2006
Loading...

Share This Page