常数差且按位与零的对数 [英] Number of pairs with constant difference and bitwise AND zero

问题描述

如何找到差异为给定常数且按位与为零的对的数量?基本上，所有(x，y)使得 x-y = k;其中k是一个给定的常数， x& y = 0;

How to find the number of pairs whose difference is a given constant and their bitwise AND is zero? Basically, all (x,y) such that x-y = k; where k is a given constant and x&y = 0;

推荐答案

一个有趣的问题.

让 k _n-1 ... k ₁ k ₀ 为 k .

Let k_n-1...k₁k₀ be the the binary representation of k.

让 l 是最小的 i 的索引，这样 k _i = 1
我们可以指出，潜在的一对解决方案 x 和 y 必须的所有位都为 i ， i< l 为零.
否则，唯一未设置第 i 位的差异 xy 的唯一方法是使 x _i = y _i = 1 和 x& y 不会设置其 i 位.

Let l be the index of the smallest i such that k_i=1
We can remark that a potential pair of solutions x and y must have all their bits i, i<l at zero.
Otherwise the only way to have a difference x-y with its ith bit unset would be to have x_i=y_i=1 and x&y will not have its ith bit unset.

现在，我们在索引 l 处的第一位到达.
情况更加复杂，因为我们有几种方法可以在 x-y 的结果中设置该位.
为此，我们必须考虑比特集 l..m ，使得 k _i = k _{i + 1} = k _{i + 2} = ... = 1 ∀ l≤ i< m 和 k _m = 0

Now we arrive at the first bit at one at index l.
The situation is more complex, as we have several ways to have this bit set in the result of x-y.
For that we must consider the set of bits l..m such that k_i=k_i+1=k_i+2=...=1 ∀l≤i<m and k_m=0

例如，如果 l = 0 和 m = 1 ，则 k 的两个LSB为01，我们可以通过以下方法获得此结果:计算01-00(1-0)或10-01(2-1).无论哪种情况，结果都是正确的(1)，并且 x 和 y 的位相反，并且在与运算后为零.

For instance, if l=0 and m=1, the two LSB of k are 01 and we can get this result by computing either 01-00 (1-0) or 10-01 (2-1). In either case, the result is correct (1) and the bits of x and y are opposite and give a zero when anded.

当序列由多个序列组成时，必须对每对连续的序列从LSB进行替换.

When the sequence is composed of several ones, the replacement must done from LSB for every pair of consecutive ones.

这里是一个例子.为简化起见，我们假设序列从第0位开始，但是泛化是立即进行的:
k = 0111
平凡的解决方案 x = k = 0111 y = 0 = 0000

Here is an example. To simplify, we assume that the sequence starts at bit 0, but the generalization is immediate :
k=0111
Trivial solution x=k=0111 y=0=0000

在LSB处将1重写为2-1:将1加到x并将1加到y
x = 0111 + 0001 = 1000 = 8 y = 0000 + 0001 = 0001
将索引1处1的位(2 ¹ )重写为4-2:将2加到x上将2加到y
x = 0111 + 0010 = 1011 y = 0000 + 0010 = 0010
将索引2处1的位(2 ² )重写为4 = 8-4:将4加到x并将4加到y
x = 0111 + 0100 = 1011 y = 0000 + 0100 = 0100

Rewrite 1 at LSB as 2-1: add 1 to x and 1 to y
x=0111+0001=1000=8 y=0000+0001=0001
Rewrite bit at 1 at index 1 (2¹) as 4-2: add 2 to x and add 2 to y
x=0111+0010=1011 y=0000+0010=0010
Rewrite bit at 1 at index 2 (2²) as 4=8-4: add 4 to x and add 4 to y
x=0111+0100=1011 y=0000+0100=0100

因此，对于由1后跟零的序列:

So, for a sequence of ones followed by a zero :

Compute the trivial solution where x=<sequence> and y=0
for every one in the sequence 
  let i be the position of this one
  generate a new solution by adding 2^i to x and y of the trivial solution

要恢复，必须以两种顺序分解数字，从LSB开始
*零是连续零的序列.
*一是一串一，后跟一个零

To resume one must decompose the number in two kind of sequences, starting at LSB
* zeroes is a sequence of consecutive zeroes
* ones is a sequence of ones followed by a zero

结果是通过替换
获得的 *零乘一组零
*通过将0、1、2、4、2 ⁱ 添加到平凡解01111..11/000 ... 000

The results are obtained by replacing
* zeroes by a set of zeroes
* ones by adding 0, 1, 2, 4, 2ⁱ to the trivial solution 01111..11/000...000

示例:

k = 22 = 16+4+2 =        0 0 0 1 0 1 1 0  
Rewrite first sequence 
011 -> 011/000 (trivial solution)
       100/001 (trivial solution+1)
       101/010 (trivial solution+2)
Rewrite second sequence
01 ->  01/00   (trivial solution)
       10/01   (trivial solution + 1)

And so there are 3*2=6 solutions
010110/000000  22/0
011000/000010  24/2
011010/000100  26/4
100110/010000  38/16
101000/010010  40/18
101010/010100  42/20

这篇关于常数差且按位与零的对数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！