# Bit

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

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));
}
``````

#bit

## Clear bits from most significant one to i

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

#bit

## Clear ith bit

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

#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

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

0

#bit

x

#bit

x

#bit

x

#bit

~x

#bit

0

#bit

x

#bit

1s

#bit

x

#bit

0 ^ 0 = 0

1 ^ 0 = 1

0 ^ 1 = 1

1 ^ 1 = 0

n XOR 0 => keep

n XOR 1 => flip

#bit

OR bit by bit

#bit

## ~ operator

Complement bit by bit

#bit