CODEWITHSUNDEEP
cbinarybittwos-complement
user11224591
user11224591

Reputation:

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

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?

Upvotes: 1

Views: 3076

Answers (3)

RobertS supports Monica Cellio
RobertS supports Monica Cellio

Reputation: 15042

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.

Upvotes: 1

Fiddling Bits
Fiddling Bits

Reputation: 8861

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

Upvotes: 0

Thomas Jager
Thomas Jager

Reputation: 5265

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.

Upvotes: 0

Related Questions