python - Python整数のビットを逆にする

Question

10 進数の整数 (例: 65) が与えられた場合、Python で基礎となるビットをどのように反転させるのですか? すなわち。次の操作:

65 → 01000001 → 10000010 → 130

この作業は次の 3 つのステップに分けられるようです。

10 進整数を 2 進表現に変換する
ビットを逆にする
10 進数に戻す

手順 2 と 3 は非常に簡単に見えますが (手順2 に関連するthisとthis SO question を参照)、手順 1 で行き詰まっています。ステップ 1 の問題は、ゼロを埋めて完全な 10 進数表現を取得することです (つまり、1000001 ではなく 65 = 01000001)。

あちこち探しましたが、何も見つからないようです。

score 54 · Accepted Answer

int('{:08b}'.format(n)[::-1], 2)

8 の代わりに任意の長さを指定できます。

b = '{:0{width}b}'.format(n, width=width)
int(b[::-1], 2)

プログラムで幅を指定できます。

score 9 · Accepted Answer

速度を上げたい場合は、 http://leetcode.com/2011/08/reverse-bits.htmlで説明されている手法を使用できます。

def reverse_mask(x):
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
    return x

score 3 · Accepted Answer

シフトとマスクを使用して、数値の i 番目のビットをテストできます。たとえば、65 のビット 6 はです(65 >> 6) & 1。右の回数だけ 1 を左にシフトすることにより、同様の方法でビットを設定できます。これらの洞察により、次のようなコードが得られます (「n」ビットのフィールドで x を反転します)。

def reverse(x, n):
    result = 0
    for i in xrange(n):
        if (x >> i) & 1: result |= 1 << (n - 1 - i)
    return result

print bin(reverse(65, 8))

score 3 · Accepted Answer

「10 進整数を 2 進表現に変換する」必要はなく、方法もありません。すべての Python 整数はバイナリとして表されます。便宜上、印刷するときに 10 進数に変換されるだけです。

この解法に従って反転問題を解きたい場合は、適切なを見つけるだけで済みますnumbits。これを手動で指定するか、整数を表すのに必要なビット数を計算することができますn( n.bit_length()Python 2.7 および 3.1 の新機能)。

ただし、65 の場合は 7 になります。なぜなら、65 がそれ以上のビットを必要とする理由がないからです。(最も近い 8 の倍数に切り上げることができます...)

score 2 · Accepted Answer

通常、単一の数値ではなく、数値の配列にこの操作を適用する必要があります。速度を上げるには、NumPy 配列を使用する方がよいでしょう。解決策は 2 つあります。

2 番目のソリューションよりも x1.34 高速:

import numpy as np
def reverse_bits_faster(x):
  x = np.array(x)
  bits_num = x.dtype.itemsize * 8
  # because bitwise operations may change number of bits in numbers
  one_array = np.array([1], x.dtype)
  # switch bits in-place
  for i in range(int(bits_num / 2)):
    right_bit_mask = (one_array << i)[0]
    left_bit = (x & right_bit_mask) << (bits_num - 1 - i * 2)
    left_bit_mask = (one_array << (bits_num - 1 - i))[0]
    right_bit = (x & left_bit_mask) >> (bits_num - 1 - i * 2)
    moved_bits_mask = left_bit_mask | right_bit_mask
    x = x & (~moved_bits_mask) | left_bit | right_bit
  return x

遅くなりますが、より理解しやすくなります ( Sudip Ghimire によって提案されたソリューションに基づく):

import numpy as np
def reverse_bits(x):
  x = np.array(x)
  bits_num = x.dtype.itemsize * 8
  x_reversed = np.zeros_like(x)
  for i in range(bits_num):
    x_reversed = (x_reversed << 1) | x & 1
    x >>= 1
  return x_reversed

python - Python整数のビットを逆にする

10 に答える 10

Related