C++ 中 Ai & Aj = 0 的有序对数量

2025 年 5 月 17 日 | 阅读 9 分钟

被称为按位与 (&) 的运算符，它作用于两个数字，并对每一对对应的位执行逻辑与操作。以下是详细说明：

1. 转换为二进制： 首先，将十进制数转换为其等效的二进制表示。

例如，我们取十进制的 6 和十进制的 3。

6 (十进制) = 0110 (二进制)

3 (十进制) = 0011 (二进制)

2. 按位与操作过程： 按位与操作涉及比较两个数字二进制表示中的每一对对应位。当两个位都为 1 时，结果中的位为 1；否则，它为 0。

示例

0110 (6 的二进制)

& 0011 (3 的二进制)

--------

0010 (2 的二进制，即十进制的 6 & 3)

执行按位与操作的结果是一个数字，其中每一位代表对两个操作数对应位应用逻辑与操作的结果。

在给定场景中，目标是确定存在多少个有序对 (Ai, Aj) 使得 Ai & Aj 等于 0，其中 Ai 和 Aj 是来自指定集合或数组的元素。

本质上，我们任务是计算集合或数组中满足其二进制表示的按位与操作结果为 0 的元素对 (Ai, Aj) 的数量。

例如，如果我们考虑集合 [2, 4 6 8]，我们的目标是找出 Ai & Aj 在其二进制形式上执行按位与操作后结果为 0 的对 (Ai, Aj)。

2 (十进制) = 0010 (二进制)
4 (十进制) = 0100 (二进制)
6 (十进制) = 0110 (二进制)
8 (十进制) = 1000 (二进制)

满足条件 Ai & Aj = 0 的对是

(2, 4)，因为 0010 & 0100 = 0000
(2, 6)，因为 0010 & 0110 = 0000
(4, 6)，因为 0100 & 0110 = 0000

因此，有 3 对 (Ai, Aj) 使得 Ai & Aj 的结果等于 0。

要解决这个问题，我们需要识别集合或数组中所有按位与操作结果为 0 的对。这包括检查每对元素并计算满足此条件的元素数量。

本文介绍了一种算法，用于计算给定非负整数数组或集合中满足 Ai 和 Aj 按位与操作结果为零的有序对 (Ai, Aj) 的数量。该方法使用嵌套循环来遍历所有可能的元素对，对每对执行按位与操作，并在结果为零时递增计数器。此解决方案的时间复杂度为 O(n^2)，其中 n 是输入数组的大小，对于大型输入来说效率不高。空间复杂度为 O(1)，因为它只使用了常量级别的额外空间。本文解释了 C++ 中的代码实现，包括嵌套循环、按位与操作和计数逻辑。

方法

我们可以按照以下步骤确定给定集合或数组中满足 Ai & Aj = 0 的对 (Ai, Aj) 的数量；

1. 使用嵌套循环

为了遍历所有元素对，我们将使用循环。
外层循环将遍历对的第一个元素 Ai。
对于每个 Ai，内层循环将遍历对的第二个元素 Aj。
这种嵌套循环结构确保我们覆盖了给定集合或数组中所有有序对 (Ai, Aj) 的组合。

2. 执行按位与操作

在嵌套循环中，对于每一对 (Ai, Aj)，我们将使用 C++ 中的 '&' 运算符执行按位与操作。
按位与操作涉及处理 Ai 和 Aj 的二进制表示。
此操作的结果将生成一个数字，其中如果 Ai 和 Aj 中对应的位都为 1，则结果中的位为 1；否则，为 0。

3. 开始计数

为了跟踪有多少对 (Ai, Aj) 的按位与结果为 0，我们将初始化一个名为 'count' 的计数器变量，其值为 0。
一旦我们对一对 (Ai, Aj) 执行了按位与操作，我们将验证其结果是否等于 0。
如果结果确实为 0，我们将 'count' 的值加 1。
在嵌套循环结束时，'count' 变量将包含所需的有序对 (Ai, Aj) 的数量，使得 Ai & Aj = 0。

4. 假设和限制

我们假设集合或列表包含数字。这个假设很重要，因为按位操作通常在 C++ 中与整数一起使用。
集合或列表中的值的大小或范围可能会构成限制。如果集合或列表很庞大，使用嵌套循环方法可能效率不高。我们可能需要探索其他方法或优化。

需要注意的是，使用循环技术会产生 O(n^2) 的时间复杂度，其中 n 代表集合或列表的大小。这是因为需要遍历所有元素对，这需要嵌套循环。在集合或列表很大的情况下，这种方法可能并不理想，促使我们寻找其他解决方案或优化。

此外，对于这种方法，空间复杂度为 O(1)，因为只需要固定的空间来存储计数器、临时变量以及执行按位与操作。

示例

让我们来看一个 C++ 代码示例，用于使用嵌套循环计算按位与结果为零的有序对。

#include <iostream>
#include <vector>

int countPairsWithBitwiseANDZero(const std::vector<int>& arr) {
    int count = 0;
    int n = arr.size();

    // Outer loop to iterate over the first element of the pair
    for (int i = 0; i < n; i++) {
        int Ai = arr[i];

        // Inner loop to iterate over the second element of the pair
        for (int j = i + 1; j < n; j++) {
            int Aj = arr[j];

            // Perform the bitwise AND operation and check if the result is 0
            if ((Ai & Aj) == 0) {
                count++;
            }
        }
    }

    return count;
}

int main() {
    std::vector<int> arr = {2, 4, 6, 8};
    int result = countPairsWithBitwiseANDZero(arr);
    std::cout << "Number of ordered pairs (Ai, Aj) such that Ai & Aj = 0:" << result << std::endl;
    return 0;
}

输出

Number of ordered pairs (Ai, Aj) such that Ai & Aj = 0: 4

说明

函数'countPairsWithBitwiseANDZero'接受一个名为 'arr' 的向量作为参数，该向量代表一个整数集合。
它首先初始化一个名为 'count' 的变量，用于计算按位与操作结果为 0 的对 (Ai, Aj) 的数量。
此外，它初始化另一个变量，用于存储输入向量 'arr' 的大小。
第一个循环，由变量 'i' 控制，遍历对的第一个元素，即 Ai。
对于每个 'Ai'，第二个循环，由变量 'j' 控制，遍历对的第二个元素，即 Aj。为了避免重复计算（例如 (Ai, Aj) 和 (Aj, Ai)），内层循环从 'i + 1' 开始。
在此循环内部，使用 '&' 运算符对 'Ai' 和 'Aj' 执行按位与操作。
如果此按位与操作 ('Ai & Aj') 的结果等于 0，则名为 'count' 的计数器变量会加 1。
一旦两个循环都完成运行，函数将返回 count 值。此计数代表 Ai 和 Aj 按位与结果为 0 的有序对的数量。
在 'main' 函数中，创建了一个名为 'arr' 的示例数组，其值为 '{2, 4 6 8}'。
调用函数 'countPairsWithBitwiseANDZero' 并将数组 'arr' 作为参数传递。
结果存储在变量 'result' 中。稍后，'result' 的值（在本例中为 3）将显示在控制台上。此计数代表三个满足 Ai & Aj = 0 条件的对：(2, 4)、(2, 6) 和 (4, 6)。

时间复杂度分析

分析时间复杂度

此方法的估算时间复杂度为 O(n^2)，其中 'n' 代表输入数组 arr 的大小。这是因为该方法涉及使用嵌套循环来遍历数组中的每一对元素。

外层循环执行 'n' 次，而每次外层循环迭代时，内层循环执行 'n - 1' 次（因为它从 i+1 开始）。因此，循环迭代的总次数可以计算如下：

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

因此，总时间复杂度确定为 O(n^2)。

由于其二次时间复杂度，这种技术对于较大的输入数组可能效率不高。不过，对于小型输入，它应该能正常运行。

在优化方面，可以考虑一些策略；

提前终止：如果在循环的某次迭代中，当前一对元素的按位与操作结果为非零值，我们可以立即终止该内层循环迭代。虽然这种优化可以带来一些改进，但在某些情况下，整体时间复杂度仍保持在 O(n^2)。
预计算：在处理输入数组之前，如果输入数组的值范围有限，我们可以预先计算该范围内所有可能对的按位与结果。虽然此初始计算将花费 O(range^2) 的时间，但后续对每个对的查找将是即时的，从而在处理大型输入时有可能降低时间复杂度。
利用位操作策略：当我们考虑输入数组的值范围时，我们可以深入研究位操作技术，以提高按位与操作的效率，并可能降低时间复杂度。这些增强措施可能带来性能提升。其影响将取决于输入数据的属性以及涉及的权衡。

分析空间复杂度

由于该解决方案只需要与输入大小无关的固定空间，因此空间复杂度保持在 O(1)。
在空间方面，不再需要进一步的优化。

边缘情况

提供的解决方案涵盖了以下被称为边缘情况的场景；

1. 空输入向量

当输入向量 'arr' 为空时，嵌套循环将不会运行。
'count' 的初始值为 0，这在处理空输入时是预期结果，因为没有可供分析的对。
例如； 'std::vector arr = {};'
预期结果； '0'

2. 单个元素的输入向量

如果输入向量 'arr' 只包含一个元素，则内层循环不会迭代，因为条件 'j < n' 总是为假（由于 'j' 从 'i + 1' 开始）。
'count' 的值将保持为 0，这与预期相符，因为没有需要评估的对组合。
例如； 'std::vector arr = {5};'
预期输出： '0'

3. 当输入向量 'arr' 完全由零组成时，任何一对元素的按位与操作结果将始终为 0。

对于每一对元素，计数都会增加，最终结果为 'n(n - 1) / 2'，其中 'n' 代表输入向量的大小。
例如，如果 'std::vector arr = {0, 0, 0, 0};'，由于大小为 4 的向量中有 6 个有序对 (0, 0)，因此预期输出将是 6。

4. 在输入向量包含负数的情况下，需要注意的是，该解决方案假定 'arr' 中为非负整数。

当存在负数时，C++ 中按位与操作的行为是与实现相关的。
此解决方案可能导致意外的结果。为了正确处理负数，可能需要进行调整或检查。

提供的方案考虑了空输入、单元素输入以及所有元素均为零的输入。如果输入中存在负数，则解决方案可能需要进行调整，以确保它们得到正确处理。

示例

让我们看另一个 C++ 示例，用于计算按位与结果等于零的对。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstring>

const int N = 15; // Maximum number of bits

long long countPairsWithBitwiseANDZero(const std::vector<int>& arr) {
    int n = arr.size();
    std::unordered_map<int, int> freq;
    long long dp[1 << N][N + 1];
    std::memset(dp, 0, sizeof(dp)); // Initialize with 0

    // Count the frequency of each element in the array
    for (int num : arr) {
        freq[num]++;
    }

    //Iterate over all possible values of the bit mask
    for (long long mask = 0; mask < (1 << N); ++mask) {
        // Handle the base case (when the last bit is set or unset)
        if (mask & 1)
            dp[mask][0] = freq[mask] + freq[mask ^ 1];
        else
            dp[mask][0] = freq[mask];

        // Compute the values for higher bit positions
        for (int i = 1; i <= N; ++i) {
            if (mask & (1 << i)) {
                dp[mask][i] = dp[mask][i - 1] + dp[mask ^ (1 << i)][i - 1];
            } else {
                dp[mask][i] = dp[mask][i - 1];
            }
        }
    }

    long long ans = 0;
    // Count the number of pairs for each element in the array
    for (int num : arr)
        ans += dp[((1 << N) - 1) ^ num][N];

    return ans;
}

int main() {
    std::vector<int> arr = {5, 4, 1, 6};
    long long result = countPairsWithBitwiseANDZero(arr);
    std::cout << "Number of ordered pairs (Ai, Aj) such that Ai & Aj = 0:" << result << std::endl;
    return 0;
}

输出

Number of ordered pairs (Ai, Aj) such that Ai & Aj = 0: 4

下一话题Kynea-numbers-in-cpp

C++ 中 Ai & Aj = 0 的有序对数量

方法

示例

边缘情况

示例

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中 Ai & Aj = 0 的有序对数量

方法

示例

边缘情况

示例

相关帖子

C++ 零法则

C++ 中的最大电影院座位分配

C++ STL 中 vector::operator= 和 vector::operator[ ]

在 C++ 中交换不同容器的子范围

C++ std::counting_semaphore, std::binary_semaphore

C++ 中的单词方块

C++ 中翻转数字的开关位（除首位和末位外）

C++ 中的 std::ctype::widen 和 do_widen

C++ 中的替换失败不是错误 (SFINAE)

C++ Tutte 定理

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器