Menu
I want to know is there any divisible rule in binary system for dividing by 3.
For example: in decimal, if the digits sum is divided by 3 then the number is devided by 3. For exmaple: 15 -> 1+5 = 6 -> 6 is divided by 3 so 15 is divided by 3.
The important thing to understand is that im not looking for a CODE that will do so.. bool flag = (i%3==0); is'nt the answer I'm looking for. I look for somthing which is easy for human to do just as the decimal law.
820
For example, to divide by 3, we can multiply by 1/3 (0.010101… 2). Note that this particular value is a repeating fraction in both decimal (0.3333…) and binary.
A number is divisible by 3, if the sum of its all digits is a multiple of 3 or divisibility by 3. Consider the multiples of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ......... In each case the sum of the digits is divisible by 3. A number is divisible by 3 if the sum of its digits is divisible by 3.
Efficient Approach: In the binary string, check for the last k bits. If all the last k bits are 0, then the binary number is evenly divisible by 2k else it is not evenly divisible.
Refer to this website: How to Tell if a Binary Number is Divisible by Three
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. The difference is 0. Thus 15 is divisible by 3.
185 = 10111001 which has 2 odd non-zero bits and 3 even non-zero bits. The difference is 1. Thus 185 is not divisible by 3.
Explanation
Consider the 2^n values. We know that 2^0 = 1 is congruent 1 mod 3. Thus 2^1 = 2 is congurent 2*1 = 2 mod 3. Continuing the pattern, we notice that for 2^n where n is odd, 2^n is congruent 1 mod 3 and for even it is congruent 2 mod 3 which is -1 mod 3. Thus 10111001 is congruent 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3 which is congruent 1 mod 3. Thus 185 is not divisible by 3.
157
i would like to divide the bits into many small pieces from right to the left ,each piece has 2 bits and if the sum of them is divisible by 3 then the number is divisible by 3. for example,we have 100111(39),we divide this number into 3 piece from right to left then we have 11,01 and 10.The sum of them is 110 which is divisible by 3 then the number 100111 is divisible by 3. example 2 : 1011010 divide them into pieces so now we have 10,10,01,01.the sum of them is 110 which is divisible by 3 then the 1011010 is divible by 3. Also note that this trick is still right for 7 but each piece must have 3 bits instead of 2
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
