bit.md

Bit

& operator

AND bit by bit

#bit

<< operator

Shift on the left

n * 2 <=> left shift by 1

n * 4 <=> left shift by 2

#bit

>> operator

Shift on the right

#bit

>>> operator

Logical shift (shift the sign bit as well)

#bit

^ operator

XOR bit by bit

#bit

Bit vector structure

Vector (linear sequence of numeric values stored contiguously in memory) in which each element is a bit (so either 0 or 1)

#bit

Check exactly one bit is set

boolean checkExactlyOneBitSet(int num) {
	return num != 0 && (num & (num - 1)) == 0;
}

#bit

Clear bits from i to 0

int clearBitsFromITo0(int num, int i) {
	int mask = (-1 << (i + 1));
	return num & mask;
}

#bit

Clear bits from most significant one to i

int clearBitsFromMsbToI(int num, int i) {
	int mask = (1 << i) - 1;
	return num & mask;
}

#bit

Clear ith bit

int clearBit(final int num, final int i) {
	final int mask = ~(1 << i);
	return num & mask;
}

#bit

Flip ith bit

int flipBit(final int num, final int i) {
	return num ^ (1 << i);
}

#bit

Get ith bit

boolean getBit(final int num, final int i) {
	return ((num & (1 << i)) != 0);
}

#bit

How to flip one bit

b ^ 1

#bit

How to represent signed integers

Use the most significative bit to represent the sign. Yet, it is not enough (problem with this technique: 5 + (-5) != 0)

Two's complement technique: take the one complement and add one

-3: 1101

-2: 1110

-1: 1111

0: 0000

1: 0001

2: 0010

3: 0011

The most significant bit still represents the sign

Max integer value: 1...1 (31 bits)

-1: 1...1 (32 bits)

#bit

Set ith bit

int setBit(final int num, final int i) {
	return num | (1 << i);
}

#bit

Update a bit from a given value

• Clear this bit
• Apply OR on the result with a 0 or 1 left shifted to its index

int updateBit(int num, int i, boolean bit) {
	int value = bit ? 1 : 0;
	int mask = ~(1 << i);
	return (num & mask) | (value << i);
}

#bit

x & 0s

0

#bit

x & 1s

x

#bit

x & x

x

#bit

x ^ 0s

x

#bit

x ^ 1s

~x

#bit

x ^ x

0

#bit

x | 0s

x

#bit

x | 1s

1s

#bit

x | x

x

#bit

XOR operations

0 ^ 0 = 0

1 ^ 0 = 1

0 ^ 1 = 1

1 ^ 1 = 0

n XOR 0 => keep

n XOR 1 => flip

#bit

| operator

OR bit by bit

#bit

~ operator

Complement bit by bit

#bit