2

最初に、「先行ゼロのバイナリ ビットを除いた整数値の補数」の意味を説明します (今後は、簡潔にするために、非先行ゼロ ビット補数または NLZ 補数と呼びます)。

たとえば、整数 92 があります。2 進数は 1011100 です。通常のビット単位の NOT または補数を実行すると、結果は -93 (符号付き整数) または 1111111111111111111111110100011 (バイナリ) になります。これは、先頭のゼロ ビットも補完されているためです。

そのため、NLZ 補数の場合、先頭のゼロ ビットは補数されず、92 または 1011100 の NLZ 補数の結果は 35 または 100011 (バイナリ) になります。演算は、入力値を 1 ビットのシーケンスで XOR することによって実行されます。イラスト: 

92:  1011100
     1111111 (xor)
     --------
     0100011 => 35


私は次のようなJavaアルゴリズムを作成しました：

public static int nonLeadingZeroComplement(int n) {
    if (n == 0) {
        return ~n;
    }
    if (n == 1) {
        return 0;
    }

    //This line is to find how much the non-leading zero (NLZ) bits count.
    //This operation is same like: ceil(log2(n))
    int binaryBitsCount = Integer.SIZE - Integer.numberOfLeadingZeros(n - 1);

    //We use the NLZ bits count to generate sequence of 1 bits as much as the NLZ bits count as complementer
    //by using shift left trick that equivalent to: 2 raised to power of binaryBitsCount.
    //1L is one value with Long literal that used here because there is possibility binaryBitsCount is 32
    //(if the input is -1 for example), thus it will produce 2^32 result whom value can't be contained in 
    //java signed int type.
    int oneBitsSequence = (int)((1L << binaryBitsCount) - 1);

    //XORing the input value with the sequence of 1 bits
    return n ^ oneBitsSequence;
}

上記のアルゴリズム、特に 1 ビット補数のシーケンス (oneBitsSequence) を生成するための行を最適化する方法についてアドバイスが必要ですか、またはより良いアルゴリズムを提案できる人はいますか?

更新:この先行しないゼロ補数の既知の用語も知りたいですか?

4

2 に答える 2