How to know number is divisible by 3 or any odd number using bitwise operator in python

Question

Am taking a number from user & I have to check whether given number is divisible by 3 or not.

Does any know the best way then plz suggest. If my input is 26 then also it's showing Divisible

#Using bitwise operator
print('Entered number is divisible by 3 or not: ')
intNumber = int( input('Enter number: ') )

if( intNumber > 0 ):
    if( 3 & (intNumber-1) ):
        print('Divisible')
    else:
        print('Not Divisible')
else:
    print('Not is less than zero')

You should first tell your algorithm or what method you tried and didn't work out, only then the SO community will come to your rescue where your code went wrong. Post your code here. Gets started with https://www.tutorialspoint.com/python/bitwise_operators_example.htm — Harshita, Sep 07 '18 at 06:27
Count the number of non-zero odd position bits and non-zero even position bits from the right. If their difference is divisible by 3, then the number is divisible by 3. https://stackoverflow.com/questions/39385971/how-to-know-if-a-binary-number-divides-by-3 — Jesse, Sep 07 '18 at 06:35
Possible duplicate of [How to know if a binary number divides by 3?](https://stackoverflow.com/questions/39385971/how-to-know-if-a-binary-number-divides-by-3) — Jesse, Sep 07 '18 at 06:36
Possible duplicate of [How does % work in Python?](https://stackoverflow.com/questions/4432208/how-does-work-in-python) — Shivid, Sep 07 '18 at 06:42
I have to use a bitwise operator, there are many ways to get solutions, but right now I have to do this using bitwise operator only — Gajanan Kolpuke, Sep 07 '18 at 06:57

Sachin · Answer 1 · 2018-09-07T06:46:02.753

0

Check given number is divisible by 17 or not

 # function to check recursively if the
 # number is divisible by 17 or not
 def isDivisible(n):
 # if n=0 or n=17 then yes
 if (n == 0 or n == 17):
    return True
# if n is less then 17, not divisible by 17
if (n < 17):
    return False
# reducing the number by floor(n/16)
return isDivisible((int)(n >> 4) - (int)(n & 15))
# driver code to check the above function
n = 12
if (isDivisible(n)):
   print(n,"is divisible by 17")
else:
   print(n,"is not divisible by 17")

edited Sep 07 '18 at 06:46

answered Sep 07 '18 at 06:45

Sachin

789
5
18

Would you like to correct your indentation? – cdarke Sep 07 '18 at 06:45
Thanks for your answer, but I it's for 17 & I need to check for 3 – Gajanan Kolpuke Sep 07 '18 at 07:09

MBo · Accepted Answer · 2018-09-07T08:07:52.040

We know school principle: if the sum of decimal digits is divisible by 9, then number is divisible by 9.
The same approach works for any base of number system b and divisor b-1: for base=4 we can check that sum of two-bits chunks is divisible by 3. We can repeat this process until all but two bits become zero.

11dec = 1011bin: 
10 + 11 = 101
01 + 01 = 10 - not divisible

21dec = 10101bin: 
01 + 01 + 01 = 11 - divisible


def divis3(x):
    while(x & (~3)):   # added more bitwiseness :) instead of (x > 3)
        sum = 0
        while (x):
            sum += x & 3  # extract two least significant bits
            x >>= 2       # shift value to get access to the next pair of bits
        x = sum
    return (x == 0 or x==3)

How to know number is divisible by 3 or any odd number using bitwise operator in python

2 Answers2