How can I get sign bit of an integer in python?

Question

I want to be able to access the sign bit of a number in python. I can do something like n >> 31 in C since int is represented as 32 bits.

I can't make use of the conditional operator and > <.

Answer 1

in python 3 integers don't have a fixed size, and aren't represented using the internal CPU representation (which allows to handle very large numbers without trouble).

So the best way is

signbit = 1 if n < 0 else 0

or

signbit = int(n < 0)

EDIT: if you cannot use < or > (which is ludicrious but so be it) you could use the fact that a-b will be positive if a is greater than b, so you could do

abs(a-b) == a-b

that doesn't use < or > (at least in the text, because abs uses it you can trust me)

Answer 2

Conceptually, the bit representation of a negative integer is padded with an infinite number of 1 bits to the left (just like a non-negative number is regarded as padded with an infinite number of 0 bits). The operation n >> 31 does work (given that n is in the range of signed 32-bit numbers) in the sense that it places the sign bit (or if you prefer, one of the left-padding bits) in the lowest bit position. You just need to get rid of the rest of the left-padding bits, which you can do with a bitwise and operation like this:

n >> 31 & 1

Or you can make use of the fact that all one bits is how −1 is represented, and simply negate the result:

-(n >> 31)

Alternatively, you can cut off all but the lowest 32 1 bits before you do the shift, like this:

(n & 0xffffffff) >> 31

This is all under the assumption that you are working with numbers that fit into a signed 32-bit int. If n might need a 64 bit representation, shift by 63 places instead of 31, and if it's just 16 bits numbers, shifting by 15 places is enoough. (If you use the (n & 0xffffffff) >> 31 variant, adjust the number of fs accordingly).

On machine code level, and-ing/negating and shifting is potentially much more efficient than using comparison. The former is just a couple of machine instructions, while the latter would usually boil down to a branch. Branching doesn't just take more machine instructions, it also has a bad influence on the pipelining and out-of-order execution of modern CPUs. But Python execution takes place in a higher-level layer than machine code execution, and therefore it's difficult to say anything about the performance impact in Python: it may depend on the context – as it would in machine code – and may therefore also be difficult to test generally. (Caveat: I don't know much about how low-level execution happens in CPython, or in Python in general. For someone who does, this might not be so difficult to say.)

If you don't know how big n is (in Python, an integer is not required to fit into any specific number of bits), you can use bit_length() to find out. This will work for integers of any size:

-(n >> n.bit_length())

The bit_length() operation might boil down to a single machine instruction, or it might actually need a loop to find the result, depending on the implementation and the underlying machine architecture. In the latter case, this should be noticeably more costly than using a constant

Final remark: in C, n >> 31 is actually not guaranteed to work like you assume, because the C language leaves it undefined whether >> does logical right shift (like you assume) or arithmetic shift right (like Python does). In some languages, these are different operators, which makes it clear what you get. In Java for instance, logical shift right is >>>, and arithmetic shift right is >>.

Answer 3

I would argue that in Python there is not really a concept of a sign bit. As far as the programmer is concerned, an int is just a type with certain behavior. You don't get access to the low-level representation. Even bin(-3) returns a "negative" binary representation: '-0b11'

However, there are ways to get the sign or the bigger if two integers without comparisons. The following approach abuses floating point math to avoid comparisons.

def sign(a):
    try:
        return (1 - int(a / (a**2)**0.5)) // 2
    except ZeroDivisionError:
        return 0

def return_bigger(a, b):
    s = sign(b - a)
    return a * s + b * (1 - s)


assert sign(-33) == 1
assert sign(33) == 0    

assert return_bigger(10, 15) == 15
assert return_bigger(25, 3) == 25
assert return_bigger(42, 42) == 42

• (a**2)**0.5 could be replaced with abs but I bet internally this is implemented with a comparison.
• The try/except is not needed if you don't care about 0 or equal integers (or there may be another horrible math workaround).
• Finally, I'd like to point out that I have absolutely no idea why on earth anybody would want to implement something like that, except for the hell of it.