Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

binary divisibility by 3 [duplicate]

Tags:

algorithm

Possible Duplicate:
Check if a number is divisible by 3

Is it true that a binary number is divisible by 3 iff it has an even number of ones? like 11000 is divisible by 3 whereas 1110 is not.

like image 955
Marley Avatar asked Nov 03 '10 10:11

Marley


People also ask

How do you check divisibility by 3 in binary?

Basically count the number of non-zero odd positions bits and non-zero even position bits from the right. If their difference is divisible by 3, then the number is divisible by 3. For example: 15 = 1111 which has 2 odd and 2 even non-zero bits.

How do you code divisible by 3?

So to check if a number is divisible by 3, you need to determine if dividing the number by three has a remainder of zero. var number = 21; if( number % 3 == 0) { //The number is divisible by three.

How do you check if a binary number is a multiple of 3?

1) Get count of all set bits at odd positions (For 23 it's 3). 2) Get count of all set bits at even positions (For 23 it's 1). 3) If the difference between the above two counts is a multiple of 3 then the number is also a multiple of 3.

Which number is divisible by 3 examples?

Consider the number 4368. We know that 9, 99, 999,… are divisible by 3, and thus the multiples of these numbers are also divisible by 3. So, the divisibility of 4368 is now dependent on the sum 4 + 3 + 6 + 8. Here, 4, 3, 6 and 8 are the digits of the number 4368.


2 Answers

No - there is a trick but it's a little more complicated than that - you have to count the number of 1s at even positions and the number of 1s at odd positions. See e.g. Check if a number is divisible by 3.

like image 147
Paul R Avatar answered Oct 29 '22 18:10

Paul R


No, that's wrong. For example 5_dec = 101_bin is not divisble by 3. To check for divisbility by three, you have to count the number of ones in even position and substract the number of ones in odd positions. If the difference is divisble by three, the original number is divisbilble by three (which, in turn, can be checked by reiterating the same rule).

like image 38
Sven Marnach Avatar answered Oct 29 '22 19:10

Sven Marnach