How does Python work on bits?

  • 1

    I got the following wrong answer:

    Input: [-2,-2,1,1,-3,1,-3,-3,-4,-2]

    Output: 4294967292

    Expected: -4

    Here is my funtion:

    def singleNumber(self, A):
        if not A:
            return A  
        s = [0]*32
        r = 0
        for i in range(0,32):
            for j in A: 
                t = j >> i
                s[i] += (j >> i) & 1
        for i in range(0,32):
            r |= s[i]%3 << i
        return r

    So, is the integer in Python a certain length of bit like c++ , 32bit?
    I check my sys.maxint, seems like it is 32 bit long, but my system is 64 bit.

    Anyone knows why?

  • 3

    you need to treat negative numbers differently. My solution is

        neg = 0;
        for a in A:
            if a < 0:
                a = -a;
                neg += 1;
            for i in xrange(nd):
                bitsum[i] = bitsum[i]+((a>>i) & 1)
        bitsum = [b%3 for b in bitsum];
        neg = -(neg % 3)*2 + 1;

    hope that helps.

  • 4

    No, the integer in Python is not a certain length. The integer sizes in Python depend on the sizes used by the C compiler that built a particular Python interpreter. Integers that fit in a C (short) int use that size, larger integers use the C long int. It's common (but not universal) for a C int to be 32 bits, and a C long int to be 64 bits.

    Like C and almost everything else, Python uses Two's Compliment Representation for (signed) integers. In this representation, the top bit (effectively) has a negative value, so the bit values of a 4-bit integer would be -8,4,2,1. All negative numbers have the top bit on, and -1 is represented by all bits on; -1 = -8+4+2+1.

    When you rightshift a negative number, the top bit must stay on to keep it negative, and it turns out that making the new leftmost bit have the same value as the old leftmost bit preserves the expected behavior that -(2n)>>1 == -(2(n-1)), with the exception of -1>>1 = -1. Since -1 is represented by all bits on, and rightshifting duplicates the leftmost bit, rightshifting a negative number repeatedly will always lead to -1. (Duplicating the existing leftmost bit is called sign extension.)

    A negative number logical-anded with 1 is either 0 or 1, it is never negative. If you start with a negative number that fits in 32 bits in two's compliment representation, recording the bits as you do will give you the correct bit pattern.

    Your bit counts in s are never negative. A nonnegative int mod 3 is also nonnegative. If you take a nonnegative int and shift it left without reaching the leftmost bit of your representation, you get another nonnegative int. If you shift it left far enough to reach the leftmost bit of your representation, then the result might be negative.

    In Python, if you take an integer that fits in a short int and left shift it too far, Python will convert it to a long int. In python, 1<<31 is converted to a long int, the same as 231. In C++, 1<<31 is not converted, so the result has only the negative-valued leftmost bit on, and has the lowest representable value. (231 is the lowest value that won't fit in 32bit two's compliment.)

    The problem with your algorithm is not the bit counting in the first loop, it's the reconstitution of the original bit pattern in the second loop. The method would work in C++, but because Python converts to long int, the bit pattern is reproduced as the lower bits of a long rather than all the bits of a short, so the leftmost bit of the pattern is interpreted as positive.

    There are at least two ways to correct this. @wenjunz's solution effectively converts to sign-magnitude representation, handles the sign bit separately, and applies the sign at the end. You can avoid adding a bit by using the leftmost bit count to initialize r before the loop, to either zero or negative.

    (This will also work if the int sizes are larger - say 64 and 128 bits, - as long as the input array only contains values that fit in 32 bits.)

  • 0

    Given a positive number i, -i is ~i + 1. You may manually do the reverse conversion in the end:

    if s[-1] % 3 == 1:
        # manually revert the thing: -i = ~i + 1
        r = -(r - 1 ^ (1 << 32) - 1)

    Note that you may not use ~ directly here since you actually only have 32 bits on r while ~ will convert all the leading 0's to 1's.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.