How to check if a number is a multiple of 6?

Question

I would like an alogrithm that would use only shift, add or subtract operations to find whether a number is a multiple of 6. So, basically just binary operations.

So far I think I should logical right shift the number twice to divide by 4 and then subtract 6 once from it. But I know something is wrong with my approach and cannot figure out what.

You can keep subtracting 6 from the number and see that it gets to zero. If the result is less than zero, then it's not divisible by 6 — Chetter Hummin, Mar 16 '12 at 04:31
Not exactly efficient, but you can implement a modulus function using only subtraction. — st0le, Mar 16 '12 at 04:31
If this is being used in a real program: don't do this. Just use `num % 6`, and let the compiler figure out what's the fastest method. More likely than not, simply using the CPU's `mod` operation will be faster than any bit-hacks you come up with. — BlueRaja - Danny Pflughoeft, Mar 16 '12 at 15:02

score 7 · Answer 1 · edited May 23 '17 at 11:56

7

1) Simple (N & 1) == 0 to check if number is divisible by 2.

2) Use the Bit hack answer (from This thread. )to check for divisibility by 3.

If both are true, your number is divisible by 6.

edited May 23 '17 at 11:56

Community

1
1

answered Mar 16 '12 at 04:35

st0le

33,375
8
89
89

1

Hmmph. Beat me by a minute, but I linked to [the hack](http://stackoverflow.com/a/3421654/487339) directly. :^) – DSM Mar 16 '12 at 04:38

Java42 · Answer 2 · 2012-03-16T06:33:32.893

0

Reference: http://wiki.answers.com/Q/How_can_you_tell_if_a_number_is_a_multiple_of_6

It is a multiple of six if BOTH of the following statements are true:
1) The last digit (ones place) is 0, 2, 4, 6, or 8.
2) When you add all the digits together, you get a multiple of 3.


Reference: http://wiki.answers.com/Q/How_can_you_tell_if_a_number_is_a_multiple_of_3

1) Start with a number N. 
2) Sum the digits of the number, and get M. 
3) If M is larger than 10, set N=M and return to stage 2.
4) Otherwise, M is now smaller than 10. If M is 0,3,6 or 9, then N is a multiple of 3

edited Mar 16 '12 at 06:33

answered Mar 16 '12 at 04:32

Java42

7,628
1
32
50

Now explain, How will you add all the digits without using division? – st0le Mar 16 '12 at 04:33
Reference: http://wiki.answers.com/Q/How_can_you_tell_if_a_number_is_a_multiple_of_6 – Java42 Mar 16 '12 at 06:31
Dude, how would you sum all the digits without using mod or div or converting it to string? – st0le Mar 16 '12 at 07:46

score 0 · Answer 3 · answered Mar 16 '12 at 04:34

0

You could try implementing a division algorithm with the primitive operations available to you. The basic long-division algorithm from 4th grade might be enough (just do things in base 2 instead of base 10, with bitshifting instead of multiplication)

answered Mar 16 '12 at 04:34

hugomg

68,213
24
160
246

score 0 · Accepted Answer · answered Mar 16 '12 at 04:35

how about keep subtracting the number by 6 until it reaches zero. If you get zero the number is divisible by 6 otherwise not. OR keep dividing the number by 2 (shift operation on binary) until the number is less than 12. then subtract 6 from it . If less than zero (not divisible ) if zero divisible. if not subtract 3 If less than zero (not divisible ) if zero divisible.

score 0 · Answer 5 · answered Mar 16 '12 at 04:41

OK. This is how I would go about it (just a first thought) :

A multiple of 6 is both a multiple of 2 and 3, so it should satisfy the divisibility criteria of 2 and 3 at the same time... So...

Check divisibility by 2 :
1. Right shift the number
2. If remainder>1, repeat 1.
3. If remainder=1, then FALSE, else continue.
  
  Checking the divisibility by 2, could obviously be also implemented by (N & 1 == 0), as stated above. This simply checks the last digit of N's binary representation : if it's 1, N is odd (thus NOT divisible by 2), if it's 0, it's perfectly divisible...
Check divisibility by 3 :
1. Substract 3.
2. If remainder>3, repeat 1.
3. If remainder>0, then FALSE, else TRUE.

score 0 · Answer 6 · answered Mar 16 '12 at 11:21

If we extend the range of operations to "bit-masking" and "bit-shifting", it's simple.

As quite a few have stated, divisibility by two is equivalent to (n & 1) == 0. Divisbility by 3 is (relatively) easy in binary. Initialize an accumulator a to 0, then repeat a += (n & 3); n = (n >> 2); until n is 0. If (and only if) a is 3 is n divisible by 3.

How to check if a number is a multiple of 6?

6 Answers6