计算数组中有多少值与给定键互补的函数

Question

我尝试做一个算法来计算矩阵中有多少元素用相同的最后 S 数字补充最后 S 位给定密钥的位数。

假设S等于3，要验证的数字是12，密钥是3。在二进制表示中，12 = (00001100) 和 3 = (00000011)。如果我们对这两个值应用异或运算，我们将获得 15 (00001111)。但是我们只考虑最后 S (3) 位，因为它们都等于 1，所以数字被补码。如果我们有相同的数字 12 但密钥 5 (00000101)，则 xor 的结果将是 return 9 (00001001)，但最后 S (3) 位不全为 1，因此不求补.

我尝试用 c++ 实现这个算法，虽然我一遍又一遍地检查它，但我似乎找不到其中的逻辑错误。我问你是因为这段代码用在我处理的一个问题中，而自动评估它的网站并没有授予它这个子问题将获得的所有分数。

int complement()
{
    //map is a globally declared matrix
    //k is the key, also global
    //S is the number of bits we take into account, also global
    int i, j, nr=0, mask, aux;
    mask = (1<<S)-1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            aux = map[i][j]^k;
            if( aux & mask == mask)
            {
                map[i][j]=0;    //overwritten as 0 meaning it is good
                nr++;
            }
            else map[i][j]=-1;  //overwritten as -1
        }
    return nr;     //how many numbers could be complemented
}

For the matrix:
15 1278 3  1278 1278 1 
16 17   18 19   254  20
21 25   26 254  254  254
27 28   29 3    2    254
2  254  4  254  254  254

The program returns:
-1  0 -1  0 0 -1 
 0 -1  0 -1 0  0 
-1 -1  0  0 0  0 
-1  0 -1 -1 0  0 
 0  0  0  0 0  0 

and nr = 20.

限制：

S <= 8
所有值和密钥 <= 9999

Answer 1

C/C++ 按位运算的运算符优先级为 "buggy".

在C/C++

aux & mask == mask

被解析为

aux & (mask == mask)

您需要改写

(aux & mask) == mask

因为否则 aux 每次都会 and-ed 与 1 无关，与掩码大小无关。

计算数组中有多少值与给定键互补的函数

Function to count how many values in an array complement with a given key

c++

algorithm

bit-manipulation