位操作如何工作？

Question

有一个问题:

"以整数n表示,在其二进制表示中找到第二个最右边的零位的从0开始的位置(保证这样的位存在),从右到左计数.

返回2position_of_the_found_bit的值."

我写了下面的解决方案,工作正常.

int secondRightmostZeroBit(int n) {
  return (int)Math.pow(2,Integer.toBinaryString(n).length()-1-Integer.toBinaryString(n).lastIndexOf('0',Integer.toBinaryString(n).lastIndexOf('0')-1))  ;
}

但下面是我最喜欢的最佳投票解决方案,因为它只有很少的字符编码和服务目的,但我无法理解.有人可以解释位操作是如何帮助实现它的.

int secondRightmostZeroBit(int n) {
  return ~(n|(n+1)) & ((n|(n+1))+1) ;
}

Answer 1

考虑一些具有至少两个0位的数字.这是一个这样的数字的例子,标记了最右边的2位(x ... x是我们不关心的位,它们可以是0或1,而1 ... 1是零或更多的序列最右边的0位右边和左边1位):

x...x01...101...1 - that's n

如果你在这个数字上加1,你会得到:

x...x01...110...0 - that's (n+1)

这意味着最右边的0位翻转为1

因此n|(n+1)会给你:

x...x01...111...1 - that's n|(n+1)

如果你添加1到n|(n+1)你得到:

x...x100........0 - that's (n|(n+1))+1

这意味着第二个最右边的0位也翻转为1

现在,~(n|(n+1))是

y...y10.........0 - that's ~(n|(n+1))

其中每个y位是相应x位的倒数

因此~(n|(n+1)) & ((n|(n+1))+1)给出

0...010.........0

其中只有1位位于0输入数字的第二个最右位的位置.