为什么(x-1)切换x的最右边设置位中的所有位? [英] Why does (x-1) toggle all the bits from the rightmost set bit of x?

问题描述

为什么此属性成立?

假设从右边开始的第k位是数字"x"中的第一个置位位.(x-1)会将每一位从右侧切换到第k位.

say the kth bit from right side is the first set bit in number 'x'. (x-1) will toggle every bit upto kth bit from right side.

我可以通过写数字的位序列来验证此属性，但是我不明白为什么该属性为true?任何人都可以通过简单的证明或直觉来帮助我，为什么这样做有效?

I can verify this property by writing the bit sequence for the numbers but I don't understand as to why this property is true? Can anyone help me with a simple proof or intuition as to why this works?

推荐答案

让我们进行手部减法

  xxx100...00
- xxx000...01
─────────────
  xxx011...11

x 表示我们不在乎的位

从右边开始， 10-1 = 1 ，从下一列借用1

Starting from the right, 10 - 1 = 1, borrowing 1 from the next column

然后下一个是 0-0 ，减去借位，这也将导致 0-1 = 1 借位1.此序列一直持续到subtrahend中的位是1，现在我们有 1-0-借贷= 1-1 = 0

Then the next one is 0 - 0, minus the borrow, which also results in 0 - 1 = 1 borrows 1. This sequence continues until the bit in subtrahend is 1, now we have 1 - 0 - borrow = 1 - 1 = 0

结果，直到最右边的设置位的所有位都将被反转

As the result, all the bits up to the rightmost set bit will be inverted

这篇关于为什么(x-1)切换x的最右边设置位中的所有位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！