2

問題は、から始まる数値の交互ビットを反転する方法LSBです。現在私がやっていることは、最初に

count = -1
while n:
   n >>= 1
   count += 1

最初に左端の設定ビットの位置を見つけ、次にループを実行してすべての代替ビットを反転します。

i = 0
while i <= count:
 num ^= 1<<i
 i += 2

このかなり退屈なループ ソリューションの代わりに、簡単なハック ソリューションはありますか? もちろん、この解では整数のサイズを推測することはできません。

4

4 に答える 4

5

私はこれがうまくいくと思います：

交互マスクを使用したビット単位の XOR は、10101010...101 つおきのビットを反転する必要があります。

`0011' の交互ビットを反転したい場合、次の表は結果を示しています:

i | m | i XOR m
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

Python XOR では、 で実現されi ^ mます。もちろん、マスクのリテラル値も決定する必要があります。これは、i数値のサイズによって異なります。

于 2012-10-27T07:59:47.460 に答える
2

以前のワンライナー ソリューション、

n ^ sum(2**i for i in range(0, len(bin(n))-2, 2))

は O(lg n) の解で、n は入力数です。以下に示す漸近的にはるかに高速なソリューションは、時間 O(lg(lg n)) で実行されます。つまり、入力数値のビット数の対数に比例する時間で実行されます。示されている二分探索はテストでは問題なく動作しましたが、おそらく改善される可能性があることに注意してください。

編集:式-1<<Lは、上位ビットが設定され、L 下位ビットがクリアされたマスクです。たとえば、python は の値として 255 を表示し、 の値(-1<<8)&255として 256 を表示します(-1<<8)&256。プログラムは、L が数値 v のビット数を超えるまで、L を 2 倍にする (より多くの下位ビットをクリアする) ことから始めます。つまり、until(-1<<L)&vはゼロです。L が 2 倍になるたびに、R を上に移動できます。次に、プログラムは二分探索を使用して、LR 差を繰り返し半分にし、 となるような L=R+1 を見つけてv&(-1<<L) == 0、v&(-1<<R) > 0v が L ビット長であることを確立します。その後、プログラムは、少なくとも L ビットの長さになるまで、交互ビット マスク k の長さを 2 倍にします。次に、L が奇数の場合、マスクを 1 ビットシフトします。（代わりにif L & 1: k = k<<1言うことができますk <<= L&1. 「代替ビット」は、MSB のすぐ下のビットから始まると解釈したことに注意してください。代わりにビット 0,2,4... を常にトグルするには、行を削除します。) 次に、 で & することにより、つまり (2**L)-1if L & 1: k = k<<1で k の下位 L ビットを取り出します。(1<<L)-1プログラムの O(lg(lg n)) 時間制限は O(1) 論理演算に依存することに注意してください。しかし、L が大きくなると (数百ビットを超えて)、1<<LO(lg n) 操作になります。

def clearaltbits(v):
    if not v:
        return 0
    L, R = 16, 0
    # Find an upper bound on # bits
    while (-1<<L) & v:
        R, L = L, 2*L
    # Binary search for top bit #
    while not (-1<<L) & v:
        m = (L+R)/2
        if (-1<<m) & v:
            R = m
        else:
            L = m
        if L==R+1: break
    print bin(v),'has',len(bin(v))-2,'bits.'
    # Make big-enough alternate-bits mask
    k, b = 0b0101010101010101, 16
    while not (-1<<L) & k:
        k = (k<<b)|k
        b += b
    if L & 1:
        k = k<<1
    k = k & ((1<<L)-1)
    print bin(k^v),'fin'


clearaltbits(3**3)
clearaltbits(5**6)
clearaltbits(7**17)
clearaltbits(13**19)

4 つの関数呼び出しからの出力を以下に示します。

0b11011 has 5 bits.
0b10001 fin

0b11110100001001 has 14 bits.
0b10100001011100 fin

0b110100111001001110000011001001100110111010000111 has 48 bits.
0b100001101100011011010110011100110011101111010010 fin

0b10011110100000000111000001101101000001011000100011000010010000111010101 has 71 bits.
0b11001011110101010010010100111000010100001101110110010111000101101111111 fin
于 2012-10-27T08:39:55.647 に答える
1

trideceth12 が与えた答えを拡張すると、マスクを計算して適用するワンライナーがあります。

n ^ sum(2**i for i in range(0, len(bin(n))-2, 2))

...つまり、LSBから始めたいと仮定します。

または、最上位のセット ビットから開始する場合:

n ^ sum(2**i for i in range(len(bin(n))-3, -1, -2))
于 2012-10-27T08:20:33.167 に答える
0

これは、任意の長さの正の整数で機能します。

def invert_alt_bits(n):
    m = 1
    while True:
        n ^= m
        m <<= 2
        if m > n: break
    return n
于 2012-10-27T10:56:35.267 に答える