Bit Manipulation

Negative number representation

We use “two’s complement” in modern computer system

XOR

when different → 1, when same →0

• X ^ X = 0 (used in cryptography a lot)
• X ^ ~X = 1s
• X ^ 1s = ~X (this is how to flip all bits)

Arithmetic shift vs logical shift

Java

• Arithmetic shift >>
• Logical shift >>>

C++

• only have >>
• if >> is applied to signed value, it is arithmetic shift
• if >> is applied to unsigned value, it is logical shift

all 1 bits

• -1 is a bit pattern with all 1s in two’s complement.
• 1 : 0001
• -1: 1110 + 1 → 1111

drawline