今天介绍一个简单一点的模板类，但我也看了一会才看懂，特别是里面的算法。

/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next

/// power of two (which means N itself if N is already a power of two).

template

struct RoundUpToPowerOfTwo;

/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a

/// helper template used to implement RoundUpToPowerOfTwo.

template

struct RoundUpToPowerOfTwoH {

enum { Val = N };

};

template

struct RoundUpToPowerOfTwoH {

enum {

// We could just use NextVal = N+1, but this converges faster. N|(N-1) sets

// the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.

Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val

};

};

template

struct RoundUpToPowerOfTwo {

enum { Val = RoundUpToPowerOfTwoH::Val };

};

这个类是用来把数字N变成第一个比它大的2的整数倍值。

N&（N-1）用来判断N本身是不是一个2的整数倍。

厉害的是N|N-1 + 1， 其中N｜N-1是用来直接把N快递地在二进制上，把最低位设置成1，再+1能快速收敛到比N大的下一个2的整数倍。

这段代码都是编译时计算，因此要看懂逻辑相当难，我写了一个python，来模拟这个过程，会更直观一些。

import sys

N = sys.argv[1]

N = int(N)

def RoundUpToPowerOfTwoH(N, bIsPowerOfTwo):

if bIsPowerOfTwo:

return N

else:

nextCheckCandidateValue = N | (N - 1)

nextCheckValue = nextCheckCandidateValue + 1

print("Next check value is {0} | {2} + 1: {1} | {3} + 1 equals {4} + 1: {5} + 1 is {6}".format(N, bin(N), N-1, bin(N-1), nextCheckCandidateValue, bin(nextCheckCandidateValue), nextCheckValue))

RoundUpToPowerOfTwo(nextCheckValue)

def RoundUpToPowerOfTwo(N):

isPowerOfTwoCheckValue = N & (N -1)

bIsPowerOfTwo = isPowerOfTwoCheckValue == 0

print("IsPowerOfTwo {0} & {2}: {1} & {3} equals {4} == 0 is {5}".format(N, bin(N), N-1, bin(N-1), isPowerOfTwoCheckValue,bIsPowerOfTwo))

RoundUpToPowerOfTwoH(N, bIsPowerOfTwo)

RoundUpToPowerOfTwo(N)

看下面这些输出会更好理解一些

conanchen@ConanChen ~ % python3 /Users/conanchen/Desktop/blog/2022/RoundUpToPowerOfTwo.py 10

IsPowerOfTwo 10 & 9: 0b1010 & 0b1001 equals 8 == 0 is False

Next check value is 10 | 9 + 1: 0b1010 | 0b1001 + 1 equals 11 + 1: 0b1011 + 1 is 12

IsPowerOfTwo 12 & 11: 0b1100 & 0b1011 equals 8 == 0 is False

Next check value is 12 | 11 + 1: 0b1100 | 0b1011 + 1 equals 15 + 1: 0b1111 + 1 is 16

IsPowerOfTwo 16 & 15: 0b10000 & 0b1111 equals 0 == 0 is True

conanchen@ConanChen ~ % python3 /Users/conanchen/Desktop/blog/2022/RoundUpToPowerOfTwo.py 17

IsPowerOfTwo 17 & 16: 0b10001 & 0b10000 equals 16 == 0 is False

Next check value is 17 | 16 + 1: 0b10001 | 0b10000 + 1 equals 17 + 1: 0b10001 + 1 is 18

IsPowerOfTwo 18 & 17: 0b10010 & 0b10001 equals 16 == 0 is False

Next check value is 18 | 17 + 1: 0b10010 | 0b10001 + 1 equals 19 + 1: 0b10011 + 1 is 20

IsPowerOfTwo 20 & 19: 0b10100 & 0b10011 equals 16 == 0 is False

Next check value is 20 | 19 + 1: 0b10100 | 0b10011 + 1 equals 23 + 1: 0b10111 + 1 is 24

IsPowerOfTwo 24 & 23: 0b11000 & 0b10111 equals 16 == 0 is False

Next check value is 24 | 23 + 1: 0b11000 | 0b10111 + 1 equals 31 + 1: 0b11111 + 1 is 32

IsPowerOfTwo 32 & 31: 0b100000 & 0b11111 equals 0 == 0 is True