Show Menu
Cheatography

Bit Manipulation Cheat Sheet (DRAFT) by [deleted]

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Abbrev­iations and Notations

LSB: Least Signif­icant Bit (right­-most)
MSB: Most Signif­icant Bit (left-­most)
a,b
(lower case): a single bit
A,B
(upper case): set of bits, e.g.
A={a_i}, i=[0,N-1]

Bit-wise operators

Bool/Bit analogy (helps to remember effect of operat­ors): 1 is TRUE, 0 is FALSE
While Bool operators (
&&
,
||
,
!
- no equiva­lence for
~
) apply to simple TRUE/FALSE operands, bit-wise operators apply to all bits of their operands (see Example block)
&
(AND): both operands have 1s
|
(OR): either or both operands have 1s
^
(XOR, aka exclusive OR): either but not both operands have 1s
~
(NOT, aka complement): 1 becomes 0; 0 becomes 1
<<
(left-­­sh­ift):
a << n
shifts all bits in
a
to the left by
n
positions and pads with 0s to the right.
>>
(right­-­s­hift):
a >> n
shifts all bits in
a
to the right by
n
positions and pads with 0s to the left
If
a
is an int,
a << n
and
a >> n
are equivalent to multip­lying an dividing respec­tively by
2n
 

1-Bit Bit-wise Operators Summary

Examples (using A = 1010; B = 1100)

&
:
A&B = 1000
|
:
A|B = 1110
^
:
A^B = 0110
:
A = 11110101
(the number of 1′s depends on the type of
A
)
<<
:
A << 2 = 0000
 

Usage

Bit accessing: 1 << 5 = 100000 TOREVIEW

Bit-wise Operators as Operations of Sets of Bits

Using
ALL_BIT
= 32/64 1s on a 32/64-bit machines
Union:
A|B
Inters­ection:
A&B
Subtra­ction:
A&(~B)
Negation:
ALL_BITS^A

Two's Complement (TsC)

Most common number system to encode pos.a dn neg. numbers in a binary number repres­ent­ation of negative integers. One's complement is the altern­ative but seeimingly never used.
In TsC, MSB used for int sign (
-
for 1,
+
for 0)
Meaning 1: Mathem­atical operation on binary numbers (the additive inverse op.)
Meaning 2: Binary signed number repres­ent­ation based on above mathem­atical operation, s.t. neg. numbers are repres­ented byt hte TsC of the abs. value
N
-bit TsC range:
[-2N-1, +(2N-1-1)]
Conversion from TsC repres­ent­ation
Conversion to TsC repres­ent­ation