5

-x が 2 進数の場合、x mod 3 を見つける方法は? 10 進数への変換を使用してから % 演算子を使用することはできません。

-例- x が 1101 の場合、出力は 1 になるはずですが、1101 を 13 に変換して % 3 で検索しないでください

4

6 に答える 6

4

「文字列」と言ったので、次の手法を追加します。

02 進数の末尾に追加すると、値が 2 倍になることに注意してください。最後に追加する場合は1、2 倍して 1 を追加します。

つまり、特定の桁までのすべての桁を処理し (この番号をその桁まで呼び出す)、いくつかのについてそれaを知っている場合、次のことがわかります。a % 3 = xx=1, 2 or 0

a0 % 3 = (2 * a) % 3 = ((2 % 3) * (a % 3)) % 3 = (2 * (a % 3)) % 3
a1 % 3 = (2 * a + 1) % 3 = ((2 % 3) * (a % 3) + (1 % 3)) % 3 = (2 * (a % 3) + 1) % 3

このようにして、次の区別を簡単に行うことができます。

Current mod | Next digit | New mod
------------+------------+---------
   0            0            0
   0            1            1
   1            0            2
   1            1            0
   2            0            1
   2            1            2

つまり、文字列を左から右にトラバースし (msbf 表記を想定) new mod、表に従って を更新できます。から始めcurrent mod = 0ます。

于 2013-11-14T13:27:06.087 に答える
1

あなたが気付いた場合2^N mod 3 = 2 if N is odd & 2^N mod 3 = 1 if N is even（それは帰納法によって証明することができます）さらにバイナリ no は 2 のべき乗の合計なので、奇数または偶数べき乗で文字列に 1 が現れるかどうかを確認し、値の実行中の合計を実行します。剰余算術には次のような定理があります。

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

例えば。

x = 1101 2 の偶数乗 (2^0,2^2) と 2 の奇数乗 (2^3) が 1 つあります。

したがって、 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"));
    }

}
于 2013-11-14T14:06:33.740 に答える
1

非常に高速で革新的です。

2 進数の 3 は 11 です。つまり、基数 10 の 11 です。したがって、奇数桁の桁の合計と偶数桁の桁の合計の差が 0 または 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);
}

詳細については、これとこれに従うことができます。

于 2013-11-14T13:26:08.130 に答える
0

A % B は A - (floor(A/B) * B) に相当します。2 進数で減算、乗算、および整数除算を実行できる場合は、%実際に使用せずに演算子をシミュレートできます。

于 2013-11-14T13:21:56.610 に答える
0

ここでの概念は、任意の 2 進数の末尾に 0 または 1 を追加すると、次のビットが設定されているかどうかに基づいて数値が 0 または 1 を加えた 2 倍になり、リマインダーも [previous_reminder*2 + (0 または 1)] になります。そして、このステップの後にリマインダーを計算するには、次のようにします。

Java コードは次のとおりです。

public static void main(String[] args) {
    int[] arr = { 1, 1, 0, 1, 1, 0, 0, 1, 1, 1};
    // Assumed first bit is always set therefore reminder will be 1.
    int reminder = 1;

    for (int i = 1; i < arr.length; i++) {
        reminder = reminder * 2 + arr[i];
        reminder = reminder % 3;
    }
    System.out.println(reminder);
}
于 2016-09-18T04:32:52.907 に答える