2公式帮助电力 [英] Power of 2 formula help

问题描述

据我所知，（2 * I ==（I ^（I - 1）+ 1）在Java将让我找到一个数是否为二的幂但有人可以解释为什么这工作

I understand that (2 * i == (i ^( i - 1) + 1) in Java will let me find if a number is a power of two. But can someone explain why this works?

推荐答案

2 * I ==（I ^（I-1））+ 1

2*i == (i ^ (i-1)) + 1

基本上，如果 I 是2的幂，将在其位模式有一个 1 。如果从减去1，那 1 位成为 1 所有的低位，而功率OF-两位将会成为0。然后你的位，这会产生一个全1位模式做了一个 XOR 。你加1到，你会得到的2下一个动力。

Basically, if i was a a power of 2, it would have a single 1 in its bit pattern. If you subtract 1 from that, all the lower bits of that 1 bit become 1, and that power-of-two bit will become 0. Then you do an XOR on the bits, which produces an all 1 bit pattern. You add 1 to that, and you get the next power of 2.

记住XOR真值表：

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

例如：

比方说， I 为256，这是该位的模式。

Let's say i is 256, which is this bit pattern.

100000000 = 2^8 = 256

100000000 - 1 = 011111111 = 2^7 + 2^6 + ... + 2^0 = 255

100000000 ^ 011111111 = 111111111 = = 2^8 + 2^7 + ... + 2^0 = 511

111111111 + 1 = 1000000000 = 2^9 = 512 = 2*i

这里有一个例子，当你不在的功率psented $ P $ 2

i = 100 = 2^6 + 2^5 + 2^2

0110 0100

0110 0100 - 1 = 99 = 2^6 + 2^5 + 2^1 + 2^0 = 0110 0011

0110 0100 ^ 0110 0011 = 0000 0111 = 2^2 + 2^1 + 2^0 = 7

0000 0111 + 1 = 000 1000 = 2^3 = 8 != (2*i)

简体版本

此外，还有这种检查的修改版本，以确定是否有一些积极，无符号整数是2的幂。

Also, there's a modified version of this check to determine if some positive, unsigned integer is a power of 2.

(i & (i-1)) == 0

基本上，同样的理由

Basically, same rationale

如果 I 是2的力量，它在其位重新$ P $一个 1 位psentation。如果你从它减去1， 1 位变为0，所有的较低位成为 1 。然后和将产生所有的 0 位模式。

If i is a power of 2, it has a single 1 bit in its bit representation. If you subtract 1 from it, the 1 bit becomes 0, and all the lower bits become 1. Then AND will produce an all 0 bit-pattern.

这篇关于2公式帮助电力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！