Setting a bit
Use the bitwise OR operator (|
) to set a bit.
number |= 1UL << n;
That will set the n
th bit of number
. n
should be zero, if you want to set the 1
st bit and so on upto n-1
, if you want to set the n
th bit.
Use 1ULL
if number
is wider than unsigned long
; promotion of 1UL << n
doesn't happen until after evaluating 1UL << n
where it's undefined behaviour to shift by more than the width of a long
. The same applies to all the rest of the examples.
Clearing a bit
Use the bitwise AND operator (&
) to clear a bit.
number &= ~(1UL << n);
That will clear the n
th bit of number
. You must invert the bit string with the bitwise NOT operator (~
), then AND it.
Toggling a bit
The XOR operator (^
) can be used to toggle a bit.
number ^= 1UL << n;
That will toggle the n
th bit of number
.
Checking a bit
You didn't ask for this, but I might as well add it.
To check a bit, shift the number n to the right, then bitwise AND it:
bit = (number >> n) & 1U;
That will put the value of the n
th bit of number
into the variable bit
.
Changing the nth bit to x
Setting the n
th bit to either 1
or 0
can be achieved with the following on a 2's complement C++ implementation:
number ^= (-x ^ number) & (1UL << n);
Bit n
will be set if x
is 1
, and cleared if x
is 0
. If x
has some other value, you get garbage. x = !!x
will booleanize it to 0 or 1.
To make this independent of 2's complement negation behaviour (where -1
has all bits set, unlike on a 1's complement or sign/magnitude C++ implementation), use unsigned negation.
number ^= (-(unsigned long)x ^ number) & (1UL << n);
or
unsigned long newbit = !!x; // Also booleanize to force 0 or 1
number ^= (-newbit ^ number) & (1UL << n);
It's generally a good idea to use unsigned types for portable bit manipulation.
or
number = (number & ~(1UL << n)) | (x << n);
(number & ~(1UL << n))
will clear the n
th bit and (x << n)
will set the n
th bit to x
.
It's also generally a good idea to not to copy/paste code in general and so many people use preprocessor macros (like the community wiki answer further down) or some sort of encapsulation.
Two's complement is a clever way of storing integers so that common math problems are very simple to implement.
To understand, you have to think of the numbers in binary.
It basically says,
- for zero, use all 0's.
- for positive integers, start counting up, with a maximum of 2(number of bits - 1)-1.
- for negative integers, do exactly the same thing, but switch the role of 0's and 1's and count down (so instead of starting with 0000, start with 1111 - that's the "complement" part).
Let's try it with a mini-byte of 4 bits (we'll call it a nibble - 1/2 a byte).
0000
- zero
0001
- one
0010
- two
0011
- three
0100
to 0111
- four to seven
That's as far as we can go in positives. 23-1 = 7.
For negatives:
1111
- negative one
1110
- negative two
1101
- negative three
1100
to 1000
- negative four to negative eight
Note that you get one extra value for negatives (1000
= -8) that you don't for positives. This is because 0000
is used for zero. This can be considered as Number Line of computers.
Distinguishing between positive and negative numbers
Doing this, the first bit gets the role of the "sign" bit, as it can be used to distinguish between nonnegative and negative decimal values. If the most significant bit is 1
, then the binary can be said to be negative, where as if the most significant bit (the leftmost) is 0
, you can say the decimal value is nonnegative.
"Sign-magnitude" negative numbers just have the sign bit flipped of their positive counterparts, but this approach has to deal with interpreting 1000
(one 1
followed by all 0
s) as "negative zero" which is confusing.
"Ones' complement" negative numbers are just the bit-complement of their positive counterparts, which also leads to a confusing "negative zero" with 1111
(all ones).
You will likely not have to deal with Ones' Complement or Sign-Magnitude integer representations unless you are working very close to the hardware.
Best Answer
Let's start with an answer to your title question.
But you ask something different on the body of your question after your example.
No! there is no overflow here. That fifth bit is the carry/borrow. Carry if you are talking about addition. Borrow if you are talking about subtraction.
Overflow occurs when the number that you trying to represent is out of the range of numbers that can be represented. In your example you are using 4-bits two's complement, that means you can represent any number in the range
-8
(1000
) up to+7
(0111
). The result of your subtraction2-1
is+1
, a number that lies within the range of representation.When we add a negative and a positive operand, the result will always be in the range of representation. Overflows occur when we add two numbers with the same sign (both positive or both negative) and the result has the opposite sign.
Most of misunderstanding surrounding carry-out and overflow comes from the fact we use the carry-out as one of the parameters to generate overflow flag. They are strongly related but they are not the same thing.
When adding numbers in two's complement, if the carry-out and the carry-on into the most significant bit (sign bit) are different that means an overflow has occurred.
Let's see two negative operands with a positive result:
The carry-out is 1 and the carry-on to sign bit (MSB) is 0.
And now, an example of two positive operands with a negative result.
The carry-out is 0 and the carry-on to sign bit (MSB) is 1.