二进制字符串余数3

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (17)

- 当x是二进制数时,如何找到x mod 3?不允许使用转换为十进制然后使用%运算符。

-eg-如果x为1101,则输出应为1,但不要将1101转换为13,然后按%3查找

提问于
用户回答回答于

如果您注意到2^N mod 3 = 2 if N is odd & 2^N mod 3 = 1 if N is even(它可以通过归纳证明)而且二进制不是2的幂的总和,那么只检查1是否出现在奇数或偶数幂的字符串中并且执行值的运行总和。模块化算术中有定理

(a+b+c)%m = ((a)%m + (b)%m + (c)%m )%m

例如。

x = 1101有2个偶数幂2(2 ^ 0,2 ^ 2)和1个奇数幂2(2 ^ 3)

因此res =(2 * 1 + 2)mod 3 = 4 mod 3 = 1

Java实现: -

public class Modulus {

    public static int modulo3(String s) {

        int end = s.length()-1;
        int sum = 0;
        for(int i =0;i<s.length();i++) {

           if(s.charAt(end)=='1') {
               if(i%2==0)
                   sum = sum + 1;
               else sum = sum + 2;
           } 

           end--; 
        }
       return(sum%3); 
    }


    public static void main(String[] args) {

        System.out.println(modulo3("1110"));
    }

}
用户回答回答于

它非常快速和创新。

如果奇数位的数字之和与偶数位的数字之和的差值为0或者可以被11整除,我们就知道一个数字可以被11整除11。

所以添加偶数放置1s并添加奇数放置1。与众不同。请检查以下程序,我们正在做同样的事情。如果你有相同的字符串也适用。

public static boolean isDivisible(int n){
    if(n<0){
        n=-n;
    }
    if(n==0)return true;
    if(n==1)return false;
    int even=0, odd=0;
    while(n!=0){
        if((n&1)==1){
            odd++;
        }
        n=n>>1;
        if(n==0)break;
        if((n&1)==1){
            even++;
        }
    }
    return isDivisible(even-odd);
}

有关更多信息,您可以按照此操作

扫码关注云+社区

领取腾讯云代金券