如何知道一个二进制数是否除以 3? [英] How to know if a binary number divides by 3?

问题描述

我想知道二进制系统中有没有除以3的除法规则.

I want to know is there any divisible rule in binary system for dividing by 3.

例如:十进制，如果数字和除以3，则数字除以3.例如:15 ->;1+5 = 6 ->6 除以 3 所以 15 除以 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.

要理解的重要一点是，我不是在寻找可以这样做的代码.. bool flag = (i%3==0);不是我正在寻找的答案.我寻找的是人类容易做的事情，就像十进制法则一样.

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.

推荐答案

参考本网站:如何判断一个二进制数是否能被三整除

基本上从右边开始计数非零奇数位和非零偶数位的数量.如果它们的差能被 3 整除，那么这个数就能被 3 整除.

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.

例如:

15 = 1111 有 2 个奇数和 2 个偶数非零位.差为 0.因此 15 可以被 3 整除.

15 = 1111 which has 2 odd and 2 even non-zero bits. The difference is 0. Thus 15 is divisible by 3.

185 = 10111001 有 2 个奇数非零位和 3 个偶数非零位.区别是 1.因此 185 不能被 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.

说明

考虑 2^n 值.我们知道 2^0 = 1 是全等的 1 mod 3.因此 2^1 = 2 是一致的 2*1 = 2 mod 3.继续这个模式，我们注意到对于 2^n 其中 n是奇数，2^n 是全等的 1 mod 3 甚至是全等的 2 mod 3 即 -1 mod 3.因此 10111001 是全等的 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3 是全等的 1 mod 3.因此 185 不能被 3 整除.

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.

这篇关于如何知道一个二进制数是否除以 3?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！