Check if a number is divisible by 8

Can You please tell how he analyze this .
How we prove this

Just think as 8 is the 3rd power of two
divide any no. 3 times by 2
and multiply no. 3 times with 2 it it is same no. then yes it is divisible by 8
Ex: n = 40
now 40 / 2 = 20
20/2 = 10
10/2 = 5
now 5 * 2 * 2 * 2 = 40 yes it is divisible

Ex : n = 36
36/2 = 18
18/2= 9
9/2 =4

4* 2 * 2 * 2 = 32 ! = 36 so 36 not divisible by 8

now to divide a no. by 8 (ie…pow(2,3) ) just right shift no. by 3
after dividing multiply by 8 just left shift by 3
U get the answer :slight_smile:

2 Likes

Yes I got It… Thanx for sharing

most welcome :slight_smile:
(20 char huuhhh)

Any number can be written as p x 1 + p x 2 + p x 4 + p x 8 + p x 16 + .... p x 2 ^ n, where p is either 0 or 1.
This can be divided into two parts, p x 1 + 2 x p + p x 4 and p x 8 + ... p x 2 ^ n.
The later part will always be divisible by 8, so, for the number to be divisible by 8, p must be equal to 0 for each p in 1 x p + 2 x p + 4 x p. Which means the first 3 bits are set to 0.
So, essentially the problem reduces to checking if the first 3 bits are unset(or 0). Now, there is an easier way to check it, you can do the & operation with binary 111 and check if the result equals to 0, i.e. n & binary(111) == 0, binary 111 is 7, so the problem reduces to n & 7 == 0.
Infact, we can now conclude a general rule of thumb from here, n will be divisible by 2 ^ i, if and only if, n & (2 ^ i - 1) == 0. This is why you will often find people anding a number with 1 to check if it is odd or even, more formally, n will be even if n & 1 == 0.
The solution used by the author of the article uses the same logic but makes it unnecessarily more complex. If you right shift a number by 3 times, it’s first 3 bits will get lost, now left shifting it again will only pad 3 0 bits in the beginning. Now, if initially all the first 3 bits equal to 0(number is divisible by 8) you will get all the bits restored after the second step(and hence the number after two shifts equals to the original number) and hence you the original number back.

3 Likes