Minimum number of bits required to represent x in two's complement

1

I was reading a book which has an exercise as:

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */

int howManyBits(int x) {
    return 0;
}

I don't even understand the question itself, how come 12 needs 5 bits, isn't that 1100, which is 4 bits? And how come -1 only need 1 bit? isn't that 1...1 is -1 in two's complement, so 32 bits are required?

c
binary
bit
twos-complement
asked on Stack Overflow Jul 2, 2020 by slowjams • edited Jul 2, 2020 by RobertS supports Monica Cellio

3 Answers

1

How come 12 needs 5 bits, isn't that 1100, which is 4 bits?

With two's complement, 1 bit more is required to classify the signedness of the value. This is (usually) the left-most bit of the bit pattern, also called "most significant bit" (MSB). If this signed bit is 1 the value is negative, if it is 0 the value is positive. So you need 5 bits to represent the value 12 = 01100, not 4.

And how come -1 only needs 1 bit?

When you only have 1 bit, this bit is used for the signedness of the value too and can either represent the values 0 or -1; -1 instead of 1 since the signed bit set to 1 means negative value.

0

A bit is used to represent the sign, 0 for positive and 1 for negative. For example, the minimum number of bits necessary to represent +12 and -12 are five:

+12 = 0 1100
-12 = 1 0100
answered on Stack Overflow Jul 2, 2020 by Fiddling Bits • edited Jul 2, 2020 by Fiddling Bits
0

Both the 12 and the -1 points can be resolved by remembering that this is 2's complement. The question asks for the minimum number of bits needed.

In a 2's complement value, the value is negative if the highest-order bit is a 1.

A 1-bit 2's complement number can represent 2 values, -1 and 0, with the bit patterns 1b and 0b respectively.

It's a little more clear if you look at 2-bit values, which can represent:

-2: 10b

-1: 11b

0: 00b

1: 01b

Note that the 1-bit 2's complement value 1b does not represent 1. Similarly, 12 requires 5 bits: 01100b. The value of the 4-bit 1100b is -4.

answered on Stack Overflow Jul 2, 2020 by Thomas Jager • edited Jul 2, 2020 by Thomas Jager

User contributions licensed under CC BY-SA 3.0