如果我有一個(gè)整數(shù)n，我該如何找到下一個(gè)數(shù)字k > n，使之k = 2^i具有某些i元素的N按位移位或邏輯運(yùn)算。示例：如果我有n = 123，我怎么能找到k = 128，它是2的冪，而不是124只能被2整除的值。這應(yīng)該很簡單，但這使我難以理解。
3 回答
慕后森
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超5個(gè)贊
對于32位整數(shù)，這是一條簡單明了的路由：
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.
這是一個(gè)更具體的例子。讓我們以數(shù)字221為例，二進(jìn)制數(shù)為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，這實(shí)際上是2的第二大冪。每個(gè)移位都將數(shù)字中所有現(xiàn)有的1位與某些先前未觸及的零重疊，最終產(chǎn)生等于原始數(shù)字中位數(shù)的1位數(shù)。給該值加1將產(chǎn)生新的2的冪。
另一個(gè)例子; 我們將使用131，即二進(jìn)制文件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
實(shí)際上，256是131的第二高冪數(shù)。
如果用于表示整數(shù)的位數(shù)本身是2的冪，則可以繼續(xù)有效且無限地?cái)U(kuò)展此技術(shù)（例如，n >> 32為64位整數(shù)添加一行）。
縹緲止盈
TA貢獻(xiàn)2041條經(jīng)驗(yàn) 獲得超4個(gè)贊
實(shí)際上有一個(gè)匯編解決方案（自80386指令集起）。
您可以使用BSR（反向位掃描）指令掃描整數(shù)中的最高有效位。
bsr掃描雙字操作數(shù)或第二個(gè)字中從最高有效位開始的位。如果這些位全為零，則清除ZF。否則，將設(shè)置ZF，并在反向掃描時(shí)將找到的第一個(gè)設(shè)置位的位索引加載到目標(biāo)寄存器中
（摘自：http : //dlc.sun.com/pdf/802-1948/802-1948.pdf）
并且比用1增加結(jié)果。
所以：
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在一個(gè)周期內(nèi)完成工作。
狐的傳說
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超3個(gè)贊
這是約翰·費(fèi)米內(nèi)拉（John Feminella）的答案，實(shí)現(xiàn)為循環(huán)，這樣它就可以處理Python的長整數(shù)：
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已經(jīng)是2的冪，它也會更快返回。
對于大于2.7的Python，對于大多數(shù)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 關(guān)注
- 490 瀏覽
添加回答
舉報(bào)
0/150
提交
取消