不用迴圈，已知a，如何求大於a的最小power of 2數的指數？

1樓：「已登出」

auto Func(unsigned long const &a)@Milo Yip

葉前輩雖然我寫了乙個版本的

但是感覺這個應該還不是最好的解決方案

有什麼指令能寫的更加優雅

2樓：

這個數是2的x次方，說明它的形式在二進位制是 0...0 1 0...0。

對int32一共也就32種可能。每個試驗一下是不是就行了嘛。當然，我這個答案和迴圈好像沒什麼區別嗎。。。。

3樓：路原

看了Milo Yip的回答，長姿勢了。我是來攪屎的。

test 用的是int，理論上支援其他長度資料#include

using namespace std;

template

class A

;template

T A::power = 0;

template

T A::num = 0;

template

bool A::bContinue = true;

int main()

{ int test_num = 2049;

if(test_num == 0return 0A::num = test_num;

A* a = new A[sizeof(int) * 8];

delete a;

cout<::power<

4樓：

學期初project寫過給32位整數的類似演算法，其實是腦筋急轉彎類，要求是不用超過1byte的整數，不用loop，不用邏輯都不行)，只用bit的! ~ & ^ | + << >>寫

解法大概是：

①已知x，令y = ~x-1

y的樣子是高位一堆1，跟著乙個0 （後面還有數字，但是可以先不管）

高位有多少個1，也就是x高位有多少位是0了，也就能算出x的最高位

比如0x00ABABAB，左邊有8個0，y裡面左邊就有8個連續的1和乙個0

比如0x0，左邊有32個0，y就是全是1

②之後有個演算法，數左邊有多少個連續的1

先處理掉無關的數字：y&=

(y>>1);

y&=(y

>>2);

y&=(y

>>4);

y&=(y

>>8);

y&=(y

>>16);

這樣一位蓋一位，只要相鄰兩位不都是1，就全被&0刷成0了（可以在紙上寫出來試試），這個數於是變成了高位一堆1，接著一堆0，現在只需要數整個int有多少個1就行了

（例子，0x00ABABABAB現在變成了0xFF000000）

接下來其實只需要把每一位加在一起就行了，但是32個操作太麻煩，用點省事的。

③這個演算法是數乙個int裡面有多少個1

先造map：

mask1 = 0x55;

mask1 = mask1 + (mask1 << 8);

mask1 = mask1 + (mask1 << 16);

用這種野蠻方式把***這個bitmap拓展到全32位, 之後再把00110011,00001111， 0000000011111111都擴充套件到32位的map，最後乙個大map其實就是各乙個byte取乙個而已

（可以無視這一步↑，因為我們當時要求不能用超過1byte大的數）

關鍵步驟

y1 = (y&mask1) + ((y >> 1)&mask1);

y2 = (y1&mask2) + ((y1 >> 2)&mask2);

...右移mask掉再相加，得到的相當於是16個和。之後，分別繼續用另外三個map，把16個和加起來變成8個和，再變成4個，再變成2個，最後再加一下兩個byte，得到了乙個和，是個數，令它為n。這個n就是int裡面總共有多少位是1

之後回到②，我們知道了高位有n個1 （因為這n個連續的1之後就全是0了）

之後回到①

數清了1，我們就知道原來的那個x的最高位有n個連續的0了

最後一步，

寫完發現樓上發了更簡單實用的，我水平比較慘，這個就當腦筋急轉彎看吧，匿了。

5樓：Milo Yip

原問題是：「不用迴圈如何求乙個數是2的多少整數次方前提已知該數必然是2的整數次方？」

~~~Bit Twiddling Hacks: Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup

If you know that v is a power of 2, then you only need the following:

static

const

intMultiplyDeBruijnBitPosition2[32

]=;r

=MultiplyDeBruijnBitPosition2

[(uint32_t)(v

*0x077CB531U

)>>27];

另外，多數 CPU 提供 Find first set 這種運算的指令，而一般編譯器都會提供 intrinsic 函式如 _BitScanForward, _BitScanForward64、 __builtin_ffs（https://

gcc.gnu.org/onlinedocs/

gcc/Other-Builtins.html）等。

不用迴圈，已知a，如何求大於a的最小power of 2數的指數？

已知子網掩碼，如何求每個子網可以容納的主機數。？

長輩的字都不能用求問邱姓女孩如何取名（已知之，雨，夢，涵，婷，萌，小，櫻，清，華不能用）諧音不可？

已知正數 x y 滿足 x y 1，如何求 5x 2 y 1 的最大值？

其他用戶還看了：

不用迴圈，已知a，如何求大於a的最小power of 2數的指數？

已知子網掩碼，如何求每個子網可以容納的主機數。？

長輩的字都不能用求問邱姓女孩如何取名（已知 之，雨，夢，涵，婷，萌，小，櫻，清，華不能用）諧音不可？

已知正數 x y 滿足 x y 1，如何求 5x 2 y 1 的最大值？

其他用戶還看了：

長輩的字都不能用求問邱姓女孩如何取名（已知之，雨，夢，涵，婷，萌，小，櫻，清，華不能用）諧音不可？