# Hacks on Bitwise Programming

## Facts and Hacks in JavaScript

In programming, we can work with bits effectively. First, let us see the definitions of each bit operation and then move onto different techniques for solving the problems. Basically, there are six operators that every language support for bit manipulation: `&`

(AND), `|`

(OR),`^`

(XOR), `<<`

(left-shift), `>>`

(right-shift), and `~`

(complement).

# Facts on Bitwise Programming

## Bitwise AND

The Bitwise AND test two binary numbers and return bit values of 1 for positions where both numbers have a one and bit values of 0 where both numbers did not have one.

// a = 10 (in binary)

var a = 2// b = 11 (in binary)

var b = 3// a & b = 10 & 11 = 10 (in binary) = 2 (in decimal)

a & b

<<2

## Bitwise OR

The bitwise OR tests two binary numbers and returns bit values of 1 for positions where either bit or both bits are one, the result of 0 only happens when both bits are 0.

`// a | b = 10 | 11 = 11 (in binary) = 3(in decimal)`

a | b

<< **3**

## Bitwise XOR

The bitwise XOR tests two binary numbers and returns bit values of 1 for positions where both bits are different; if they are the same then the result is 0.

`// a ^ b = 10 ^ 11 = 01 (in binay) = 1 (in decimal)`

a ^ b

<< **1**

## Bitwise Left Shift

The bitwise left shift moves all bits in the number to the left and fills vacated bit positions with 0 (left-shift) or 1 (unsigned left shift).

// c = 0101 (in binary)

var c = 5// bitwise left shift: c << 1 = 1010 (in binary) = 10 (in decimal)

c << 1

<<1

**Bitwise Right Shift**

The bitwise right shift moves all bits in the number to the right.

`// c >> 1 = 010 (in binary) = 2 (in decimal)`

c >> 1

<< **2**

## Bitwise Complement

The bitwise complement inverts the bits in a single binary number.

`// ~c -> 1010 (in binary) -> 10 (in decimal), 2’s compliment of 10 will be -6.`

~c

<< **-6**

# Hacks on Bitwise Programming

## Checking Whether Number is Power of 2 or Not

Given number `n`

, to check whether the number is in `2^n`

form for not, we can use the expression: `if(n & n — 1 == 0)`

.

// n = 10000

var n = 16 // 2⁴// n — 1 = 15 (in decimal) = 01111

// n & (n — 1) = 10000 & 01111 = 0

n & (n — 1)

<<0

## Multiplying Number by Power of 2

For a given number `n`

, to multiply the number with `2^k`

we can use the expression: `n ≪ k`

*.*

var n = 16// 16*(2^1) = 32

n << 1

<<32

## Dividing Number by Power of 2

For a given number `n`

, to divide the number with `2^k`

we can use the expression: `n ≫ k`

.

var n = 16// 16/(2²) = 4

n >> 2

<<4

## Performing Average without Division

Is there a bit-twiddling algorithm to replace `mid = (low + high) / 2`

(used in Binary Search and Merge Sort) with something much faster?

We can use `mid = (low + high) >> 1`

.

## Finding Modulo of a Given Number

For a given number `n`

, to find the `%8`

we can use the expression: `n & 0x7`

. Similarly, to find `%32`

, use the expression: `n & 0x1F`

.

var n = 20// 20%8 = 4

n & 0x7

<<4

Similarly, we can find modulo value of any number.

## Checking Whether K-th Bit is Set or Not

Let us assume that the given number is `n`

. Then for checking the `K-th`

bit we can use the expression: `n & (1 ≪ K 1)`

. If the expression is true then we can say the `K-th`

* *bit is set (that means, set to 1).

// n = 01001011 (in binary)

var n = 75

var k = 4// 1 << k — 1 = 00001000 (in binary)

// n & (1 << k — 1) = 01001011 & 00001000 = 00001000 = 8 (in decimal)n & (1 << k — 1)

<<8

## Setting K-th Bit

For a given number `n`

, to set the `K-th`

bit we can use the expression: `n | 1 ≪ (K — 1)`

. Let assume that we need to set 3rd bit of n.

// n = 01001011 (in binary)

var n = 75

var k = 3// 1 << k — 1 = 00000100 (in binary)

// n | (1 << k — 1) = 01001011 | 00000100 = 01001111 (in binary) = 79 (in decimal)

n | (1 << k — 1)

<<79

## Clearing K-th Bit

To clear `K-th`

bit of a given number `n`

, we can use the expression: `n & ~(1 ≪ K — 1)`

.

// n = 01001011 (in binary)

var n = 75

var k = 3// 1 << k — 1 = 00000100 (in binary)

// n & (1 << k — 1) = 01001011 & 00000100 = 0 (in binary) = 0 (in decimal)

n & (1 << k — 1)

<<0

## Toggling k-th bit of a number

For a given number `n`

, if `k-th`

bit is `0`

, then toggle it to `1`

and if it is `1`

then, toggle it to `0`

. We can use the expression: `n ^(1 ≪ k –1)`

.

// n = 01001011 (in binary) -> toggle(n, k) = 01001111

var n = 75

var k = 3// 1 << k — 1 = 00000100 (in binary)

// n ^ (1 << k — 1) = 01001011 ^ 00000100 = 01001111 (in binary) = 79 (in decimal)

n ^ (1 << k — 1)

<<79

## Toggling Rightmost One Bit

For a given number `n`

, for toggling rightmost one bit we can use the expression: `n & n — 1`

.

// n = 01001011 (in binary)

var n = 75// n — 1 = 74 = 01001010

// n & n — 1 = 01001011 & 01001010 = 01001010 = 74

n & n — 1

<<74

Thanks for reading 😘, goodbye 👋, and don’t forget to 👏 up to 50 times and follow!