6

与えられた 2 つの数字がグレイ コード シーケンスの連続した数字であるかどうか、つまり、グレイ コード シーケンスが言及されていないと仮定してグレイ コードの隣人であるかどうかを調べるという問題の解決策を考え出そうとしています。

さまざまなフォーラムで検索しましたが、正しい答えが得られませんでした。これに対する解決策を提供できれば素晴らしいことです。

問題への私の試み - 2 つの整数を 2 進数に変換し、両方の数字の数字を別々に追加し、2 つの数字の数字の合計の差を見つけます。差が 1 の場合、それらはグレイ コード ネイバーです。

しかし、これはすべての場合にうまくいくとは思えません。どんな助けでも大歓迎です。よろしくお願いします!!!

4

9 に答える 9

32

実際には、他の答えのいくつかは間違っているようです: 隣り合う 2 つのバイナリ反射グレイ コードが 1 ビットだけ異なることは事実です (「グレイ コード シーケンス」とは、Frank Gray によって説明されている元のバイナリ反射グレイ コード シーケンスを意味すると仮定します)。 ）。ただし、1 ビット異なる 2 つのグレイ コードが隣接a => bしているとは限りません ( という意味ではありませんb => a)。たとえば、グレイ コード 1000 と 1010 は 1 ビットだけ異なりますが、隣接していません (1000 と 1010 はそれぞれ 10 進数で 15 と 12 です)。

a2 つのグレー コードとbが隣接しているかどうかを知りたい場合は、 かどうかを確認する必要がありますprevious(a) = b OR next(a) = b。与えられたグレイ コードの場合、右端のビットを反転することによって 1 つの隣接ビットを取得し、右端のセット ビットの左にあるビットを反転することによってもう 1 つの隣接ビットを取得します。グレイ コード 1010 の場合、近隣は 1011 と 1110 です (1000 はそれらの 1 つではありません)。

これらのビットの 1 つを反転することによって前または次のネイバーを取得するかどうかは、実際にはグレイ コードのパリティに依存します。ただし、両方の隣人が必要なので、パリティをチェックする必要はありません。次の疑似コードは、2 つのグレイ コードが隣接しているかどうかを示します (C のようなビット演算を使用)。

function are_gray_neighbours(a: gray, b: gray) -> boolean
    return b = a ^ 1 OR
           b = a ^ ((a & -a) << 1)
end

上記のビット トリック:a & -a数値の中で最も右に設定されたビットを分離します。そのビットを 1 ポジション左にシフトして、反転する必要があるビットを取得します。

于 2014-12-06T14:32:00.170 に答える
1

仮定: 入力 a および b は、バイナリ反射グレイ コードのグレイ コード シーケンスです。つまり、a と b のビット エンコーディングはバイナリ グレイ コード表現です。

#convert from greycode bits into regular binary bits
def gTob(num): #num is binary graycode 
    mask = num >> 1
    while mask!=0:
        num = num^mask
        mask >>= 1
    return num; #num is converted 

#check if a and b are consecutive gray code encodings
def areGrayNeighbors(a,b):
    return abs(gTob(a) - gTob(b)) == 1

いくつかのテストケース:

  • areGrayNeighbors(9,11) --> True ((1001, 1011) は 1 ビットだけ異なり、10 進数表現では連続する数値であるため)
  • areGrayNeighbors(9,10) --> False
  • areGrayNeighbors(14,10) --> 真

参考文献: 上記で使用されているメソッド gTob() は、この投稿の Rodrigo によるものです。グレイ コードの隣人

于 2014-12-27T23:30:42.730 に答える
0

2 つの数値がグレイ コード シーケンスの場合、それらは 2 進数で 1 桁異なります。つまり、2 つの数値の排他的 OR は 2 の累乗を返します。したがって、XOR を見つけて、結果が 2 の累乗であるかどうかを確認します。

このソリューションは、上記の CodeKaichu によって記述されたすべてのテスト ケースでうまく機能します。いずれにしても失敗するかどうか知りたいです。

public boolean grayCheck(int x, int y) {
       int z = x^y;
       return (z&z-1)==0;
}
于 2015-04-16T03:28:58.513 に答える
0 
public int checkConsecutive2(int b1, int b2){
    int x =  (b1 ^ b2);

    if((x & (x - 1)) !=0){
      return 0;
    }else{
      return 1;
    }

}
于 2015-03-25T21:32:32.620 に答える
-1

次のように、2 つの数値が 1 ビット異なるかどうかを確認できます。この方法では、2 進数の長さの違いが考慮されます。たとえば、11 (1011) と 3 (11) の出力は true として返されます。また、これはグレイ コード隣接の 2 番目の基準を解決しません。しかし、数値が 1 ビット異なるかどうかだけを確認したい場合は、以下のコードが役に立ちます。

class Graycode{
    public static boolean graycheck(int one, int two){
        int differences = 0;
        while (one > 0 || two > 0){
            // Checking if the rightmost bit is same
            if ((one & 1) != (two & 1)){
                differences++;
            }
            one >>= 1;
            two >>= 1;
        }
        return differences == 1;
    }
    public static void main(String[] args){
        int one = Integer.parseInt(args[0]);
        int two = Integer.parseInt(args[1]);
        System.out.println(graycheck(one,two));
    }
}
于 2015-03-02T03:01:00.397 に答える
-7

私もインタビューでこの質問を解決しなければなりませんでした。2 つの値がグレイ コード シーケンスになるための条件の 1 つは、それらの値が 1 ビットだけ異なることです。この問題の解決策は次のとおりです。

def isGrayCode(num1, num2):
    differences = 0
    while (num1 > 0 or num2 > 0):
        if ((num1 & 1) != (num2 & 1)):
            differences++
        num1 >>= 1
        num2 >>= 1
    return differences == 1
于 2014-11-30T22:38:09.513 に答える