[Solved] What happens when bitwise AND is applied to negative numbers?

Question

In C, in the result of the binary &, each bit depends on the two corresponding bits in the operands. If the bit in the same position is set (1) in both operands, it is set in the result. If it is clear (0) in either operand, it is clear in the result. For example, given bits 0011 and 0101, the & operator would produce 0001, because only in the last position is the bit set in both operands.

You likely already know that positive integers are represented with binary. The bit positions are numbered starting from 0 on the “right”, then 1 for the next position, 2, 3, and so on. The bit in position i represents a value of 2ⁱ, so bit 0 represents 1, bit 1 represents 2, bit 2 represents 4, bit 3 represents 8, bit 4 represents 16, and so on. The value represented by all the bits is the sum of the values of the bits that are set to 1. So 101 represents 5, because the bits for 2² = 4 and 2⁰ = 1 are set, and 4+1 = 5.

The C standard specifies three rules that a C implementation may use to represent negative numbers (in C 2018 6.2.6.2 2):

One of the bits represents a sign. If the sign bit is 0, the value is the same as above. If the sign bit is 1, the value is negated. So, if the first bit is the sign bit, then 5 is 0101 is 5, and −5 is 1101. This is called sign and magnitude.
One of the bits represents a sign, and, if a number is negative, all of the bits are inverted. So 5 is 0101, and −5 is 1010. This is called one’s complement.
One of the bits represents a sign, and, if the number is negative (let’s call it x), the bits are set in the pattern that would be used for 2^N−x, where N is the number of bits. For example, for four bits, 2^N = 16, and 5 is 0101, and −5 is represented with the bits for 16−5 = 11, which are 1011. This is called two’s complement.

In early computer hardware and software, all of the above were tried. The last, two’s complement, is overwhelming dominant in modern computing for integers. (Most floating-point uses sign and magnitude.) Nonetheless, the C standard still permits implementations to use any of the methods.

Because of this, the result of -10 & 5 is implementation-dependent. I will illustrate using eight bits, with a space to group them into two sets of four bits for visibility:

With two’s complement:

−10 is represented with 1111 0110 (256 − 10 = 246 = 128+64+32+16+4+2), 5 uses 0000 0101, and −10 & 5 is 0000 0100, which represents 4.

With one’s complement:

−10 is represented with 1111 0101, 5 uses 0000 0101, and −10 & 5 is 0000 0101, which represents 5.

With sign and magnitude:

−10 is represented with 1000 1010, 5 uses 0000 0101, and -10 & 5 is 0000 0000, which represents 0.

Thus, a C implementation that conforms to the C standard could produce 0, 4, or 5 for -10 & 5, but 4 is by far the most common result.

Accepted Answer

In C, in the result of the binary &, each bit depends on the two corresponding bits in the operands. If the bit in the same position is set (1) in both operands, it is set in the result. If it is clear (0) in either operand, it is clear in the result. For example, given bits 0011 and 0101, the & operator would produce 0001, because only in the last position is the bit set in both operands.

You likely already know that positive integers are represented with binary. The bit positions are numbered starting from 0 on the “right”, then 1 for the next position, 2, 3, and so on. The bit in position i represents a value of 2ⁱ, so bit 0 represents 1, bit 1 represents 2, bit 2 represents 4, bit 3 represents 8, bit 4 represents 16, and so on. The value represented by all the bits is the sum of the values of the bits that are set to 1. So 101 represents 5, because the bits for 2² = 4 and 2⁰ = 1 are set, and 4+1 = 5.

The C standard specifies three rules that a C implementation may use to represent negative numbers (in C 2018 6.2.6.2 2):

One of the bits represents a sign. If the sign bit is 0, the value is the same as above. If the sign bit is 1, the value is negated. So, if the first bit is the sign bit, then 5 is 0101 is 5, and −5 is 1101. This is called sign and magnitude.
One of the bits represents a sign, and, if a number is negative, all of the bits are inverted. So 5 is 0101, and −5 is 1010. This is called one’s complement.
One of the bits represents a sign, and, if the number is negative (let’s call it x), the bits are set in the pattern that would be used for 2^N−x, where N is the number of bits. For example, for four bits, 2^N = 16, and 5 is 0101, and −5 is represented with the bits for 16−5 = 11, which are 1011. This is called two’s complement.

In early computer hardware and software, all of the above were tried. The last, two’s complement, is overwhelming dominant in modern computing for integers. (Most floating-point uses sign and magnitude.) Nonetheless, the C standard still permits implementations to use any of the methods.

Because of this, the result of -10 & 5 is implementation-dependent. I will illustrate using eight bits, with a space to group them into two sets of four bits for visibility:

With two’s complement:

−10 is represented with 1111 0110 (256 − 10 = 246 = 128+64+32+16+4+2), 5 uses 0000 0101, and −10 & 5 is 0000 0100, which represents 4.

With one’s complement:

−10 is represented with 1111 0101, 5 uses 0000 0101, and −10 & 5 is 0000 0101, which represents 5.

With sign and magnitude:

−10 is represented with 1000 1010, 5 uses 0000 0101, and -10 & 5 is 0000 0000, which represents 0.

Thus, a C implementation that conforms to the C standard could produce 0, 4, or 5 for -10 & 5, but 4 is by far the most common result.