seclan のほえほえルーム

2のべき乗高速判定アルゴリズム (1999/06/11 [金])

　ある値が 2 のべき乗かどうかを調べるために、わざわざループを使っていませんか? もっといい方法があります。それがこの式 (x & (x-1)) です。この値が0だと2のべき乗です。ただし、x=0の時は気をつける必要があります。

x	x-1	x & (x-1)	べき
000	111	000	×
001	000	000	○
010	001	000	○
011	010	010	×
100	011	000	○
101	100	100	×
110	101	100	×
111	110	110	×

by seclan

配信

x	x-1	x & (x-1)	べき
000	111	000	×
001	000	000	○
010	001	000	○
011	010	010	×
100	011	000	○
101	100	100	×
110	101	100	×
111	110	110	×

x	x-1	x & (x-1)	べき
000	111	000	×
001	000	000	○
010	001	000	○
011	010	010	×
100	011	000	○
101	100	100	×
110	101	100	×
111	110	110	×

x	x-1	x & (x-1)	べき
000	111	000	×
001	000	000	○
010	001	000	○
011	010	010	×
100	011	000	○
101	100	100	×
110	101	100	×
111	110	110	×