如果我有一個整數n，我該如何找到下一個數字k > n，使之k = 2^i具有某些i元素的N按位移位或邏輯運算。示例：如果我有n = 123，我怎么能找到k = 128，它是2的冪，而不是124只能被2整除的值。這應該很簡單，但這使我難以理解。
3 回答
慕后森
TA貢獻1802條經驗 獲得超5個贊
對于32位整數，這是一條簡單明了的路由：
unsigned int n;
n--;
n |= n >> 1; // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2; // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++; // The result is a number of 1 bits equal to the number
// of bits in the original number, plus 1. That's the
// next highest power of 2.
這是一個更具體的例子。讓我們以數字221為例，二進制數為11011101：
n--; // 1101 1101 --> 1101 1100
n |= n >> 1; // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2; // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4; // ...
n |= n >> 8;
n |= n >> 16; // 1111 1111 | 1111 1111 = 1111 1111
n++; // 1111 1111 --> 1 0000 0000
第九位有一位，它表示2 ^ 8，即256，這實際上是2的第二大冪。每個移位都將數字中所有現有的1位與某些先前未觸及的零重疊，最終產生等于原始數字中位數的1位數。給該值加1將產生新的2的冪。
另一個例子; 我們將使用131，即二進制文件10000011：
n--; // 1000 0011 --> 1000 0010
n |= n >> 1; // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2; // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4; // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8; // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16; // operations produce no effect.)
n++; // 1111 1111 --> 1 0000 0000
實際上，256是131的第二高冪數。
如果用于表示整數的位數本身是2的冪，則可以繼續有效且無限地擴展此技術（例如，n >> 32為64位整數添加一行）。
縹緲止盈
TA貢獻2041條經驗 獲得超4個贊
實際上有一個匯編解決方案（自80386指令集起）。
您可以使用BSR（反向位掃描）指令掃描整數中的最高有效位。
bsr掃描雙字操作數或第二個字中從最高有效位開始的位。如果這些位全為零，則清除ZF。否則，將設置ZF，并在反向掃描時將找到的第一個設置位的位索引加載到目標寄存器中
（摘自：http : //dlc.sun.com/pdf/802-1948/802-1948.pdf）
并且比用1增加結果。
所以：
bsr ecx, eax //eax = number
jz @zero
mov eax, 2 // result set the second bit (instead of a inc ecx)
shl eax, ecx // and move it ecx times to the left
ret // result is in eax
@zero:
xor eax, eax
ret
在較新的CPU中，您可以使用快得多的lzcnt指令（aka rep bsr）。lzcnt在一個周期內完成工作。
狐的傳說
TA貢獻1804條經驗 獲得超3個贊
這是約翰·費米內拉（John Feminella）的答案，實現為循環，這樣它就可以處理Python的長整數：
def next_power_of_2(n):
"""
Return next power of 2 greater than or equal to n
"""
n -= 1 # greater than OR EQUAL TO n
shift = 1
while (n+1) & n: # n+1 is not a power of 2 yet
n |= n >> shift
shift <<= 1
return n + 1
如果n已經是2的冪，它也會更快返回。
對于大于2.7的Python，對于大多數N來說，這更簡單，更快：
def next_power_of_2(n):
"""
Return next power of 2 greater than or equal to n
"""
return 2**(n-1).bit_length()
- 3 回答
- 0 關注
- 492 瀏覽
添加回答
舉報
0/150
提交
取消