C++ 中范围内所有子数组按位与和的查询

2024年8月29日 | 阅读 10 分钟

引言

在本文中，任务是计算给定数组索引范围内所有子数组的按位与（bitwise AND）运算结果之和。按位与是一种运算，它将两个二进制数进行逻辑与运算，对每一对对应的位进行操作，生成一个新的二进制数。

程序

#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the sum of bitwise AND all subarrays in a range
int sumBitwiseAndInRange(int arr[], int n, int left, int right) {
    int result = 0;
    // Iterate through each bit position (32 bits for integers)
    for (int bit = 0; bit < 32; ++bit) {
        int countOnes = 0;  // Count of set bits at the current bit position
        // Iterate through each element in the given range
        for (int i = left; i <= right; ++i) {
            // Check if the bit at the current position is set (1)
            if ((arr[i] & (1 << bit)) != 0) {
                countOnes++;
            }
        }
        // If the count of set bits is equal to the number of elements in the range,
        // it means that the AND of the bit at the current position will be 1 in all subarrays.
        // So, set the corresponding bit in the result.
        if (countOnes == (right - left + 1)) {
            result |= (1 << bit);
        }
    }
    return result;
}
int main() {
    // Example usage
    int arr[] = {5, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int left = 0, right = 2;
    // Calculate the sum of bitwise AND of all subarrays in the given range
    int result = sumBitwiseAndInRange(arr, n, left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

输出

Sum of bitwise AND of all subarrays in the range [0, 2] is: 0

说明

主要目标

此代码的主要目标是查找数组中给定范围内所有子数组的按位与运算结果之和。

函数 sumBitwiseAndInRange

此函数接受三个参数：**数组 (arr)**、**数组的大小 (n)** 以及由索引指定的范围 **(left 和 right)**。

它使用循环遍历每个 **位位置（0 到 31）**，因为整数通常用 32 位表示。

按位与运算

在循环内部，它计算当前位置的位在指定范围内（从 left 到 right）的数组元素中被设置为 1 的次数。

设置位检查

如果当前位置的设置位数等于范围内的元素数量，则意味着该位在范围内的所有子数组的 AND 运算结果都将始终为 1。因此，它将在结果中设置相应的位。

结果累加

最终结果是通过组合所有位的按位或（bitwise OR）来累加的。

主函数

main 函数演示了 sumBitwiseAndInRange 函数的用法，使用了一个示例数组 ({5, 2, 8}) 和指定的范围（left = 0, right = 2）。

它打印出指定范围内所有子数组的按位与计算总和。

复杂度分析

时间复杂度

代码的时间复杂度主要取决于两个循环
外层循环为每个位位置运行 **（对于 32 位整数，运行 32 次）**。
内层循环为指定 **范围（从 left 到 right）** 中的每个元素运行。
因此，总时间复杂度可以表示为 **O(32 * (right - left + 1))**，简化为 **O(right - left)**。

空间复杂度

代码的空间复杂度相对较低且是常数。它使用几个整数变量 **(result, bit, countOnes, i)**，这些变量占用的空间不取决于输入大小。因此，我们可以将空间复杂度视为 **O(1)** 或常数。

方法 1：观察规律

这种方法背后的思想是观察一系列连续数字的按位与运算，并认识到结果是它们二进制表示的公共前缀。之后，我们可以找到这个公共前缀并将其转换回十进制以获得最终结果。

程序

#include <iostream>
using namespace std;
int findCommonPrefix(int x, int y) {
    int shift = 0;
   // Keep shifting until the bits at the current position are different
    while (x < y) {
        x >>= 1;
        y >>= 1;
        shift++;
    }
    // Shift the common prefix back to the original position
    return x << shift;
}
int sumBitwiseAndInRange(int left, int right) {
    // Find the common prefix of the binary representation
    int commonPrefix = findCommonPrefix(left, right);
    return commonPrefix;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

输出

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

说明

findCommonPrefix 函数接受两个 **整数 (x 和 y)**，并查找它们二进制表示的公共前缀。它通过右移两个数字直到它们在当前位置的位不同来实现。然后，它将公共前缀移回其原始位置。

sumBitwiseAndInRange 函数调用 findCommonPrefix 来获取给定 **范围（left 到 right）** 的二进制表示的公共前缀。

main 函数演示了 sumBitwiseAndInRange 的用法，使用了一个示例 **范围（left = 5, right = 8）**。它计算并打印指定范围的按位与和。

复杂度分析

时间复杂度

findCommonPrefix 函数的时间复杂度取决于两个数字 **(x 和 y)** 中较小的那个的二进制表示中的位数。findCommonPrefix 内部的循环会迭代直到当前位置的位不同，在最坏的情况下，需要 **O(log(min(x, y)))** 次迭代。
sumBitwiseAndInRange 函数调用 findCommonPrefix，因此其时间复杂度也为 **O(log(min(left, right)))**。
main 函数和其余代码以常数时间运行，因为它们涉及基本操作。
总时间复杂度为 **O(log(min(left, right)))**。

空间复杂度

空间复杂度非常低且是常数。该算法只使用几个整数变量 **(shift, commonPrefix, left, right, result)**，这些变量占用的空间不取决于输入大小。
总空间复杂度为 **O(1)** 或

方法 2：使用位操作

这种方法背后的思想是对指定范围内的所有元素执行 **按位与** 运算，并跟踪每个位位置的结果。

程序

#include <iostream>
#include <climits>
using namespace std;
int sumBitwiseAndInRange(int left, int right) {
    // Initialize the result as INT_MAX (all bits set to 1)
    int result = INT_MAX;
    // Iterate through each bit position
    for (int bitPos = 31; bitPos >= 0; --bitPos) {
        // Check if the bit at the current position is set (1) in both left and right
        if ((left & (1 << bitPos)) && (right & (1 << bitPos))) {
            // If set, set the corresponding bit in the result
            result |= (1 << bitPos);
        } else {
            // If not set in both left and right, clear the corresponding bit in the result
            result &= ~(1 << bitPos);
        }
    }
    return result;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

输出

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

说明

sumBitwiseAndInRange 函数接受两个整数 **(left 和 right)**，表示范围。
它将结果变量初始化为 **INT_MAX**，以表示所有位都 **设置为 1**。
它迭代每个位位置（从最高有效位到最低有效位）。
对于每个位位置，它检查该位在 left 和 right 中是否都设置了（为 1）。
如果该位在两者中都设置了，则在结果中设置相应的位。
如果该位在两者中都未设置，则在结果中清除相应的位。
最终结果是指定范围内的按位与之和。
main 函数演示了 sumBitwiseAndInRange 的用法，使用了一个示例范围 **(left = 5, right = 8)**。它计算并打印指定范围的按位与 **（bitwise AND）** 和。

复杂度分析

时间复杂度

sumBitwiseAndInRange 函数的时间复杂度主要由迭代每个位位置的循环决定。该循环运行的常数次迭代（在本例中为 32 次），使时间 **复杂度为 O(1)**。

空间复杂度

代码的空间复杂度非常低且是常数。该算法只使用几个整数变量 **(result, left, right, bites)**，这些变量占用的空间不取决于输入大小。

此代码的总时间和空间复杂度为 **O(1)** 或常数。

方法 3：使用按位移位

它有助于识别 left 和 right 的公共 **最左位**。将公共最左位右边的所有位设置为 0。

程序

#include <iostream>
using namespace std;
int sumBitwiseAndInRange(int left, int right) {
    int shift = 0;
    // Keep shifting until left and right become equal
    while (left < right) {
        left >>= 1;   // Right-shift 'left'
        right >>= 1;  // Right-shift 'right'
        shift++;      // Increment shift for each right-shift
    }
    // Left-shift either 'left' or 'right' by 'shift' to restore common leftmost bits
    return left << shift;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

输出

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

说明

函数 sumBitwiseAndInRange

该函数接受两个整数 **left** 和 **right**，表示范围。

它初始化一个变量 shift 为 0，该变量将跟踪需要移位的位数。

while 循环持续进行，直到 left 和 right 相等。

在每次迭代中，left 和 right 都向右移位 1，并且 shift 递增。

循环结束后，它将 left 或 right 向左移位 shift 次，以恢复公共最左位。

返回最终结果。

主函数

main 函数演示了 sumBitwiseAndInRange 的用法，使用了一个示例范围 **(left = 5, right = 8)**。

它计算并打印指定范围的 **按位与** 和。

复杂度分析

时间复杂度

sumBitwiseAndInRange 函数的时间复杂度主要由 while 循环决定。该循环一直运行到 left 和 right 相等，在最坏情况下需要对数时间。

时间复杂度为 **O(log(min(left, right)))**。

空间复杂度

空间复杂度非常 **低** 且 **恒定**。该算法只使用几个整数变量 **(left, right, shift)**，这些变量占用的空间不取决于输入大小。

空间复杂度为 **O(1)** 或常数。

方法 4：使用公共前缀位掩码

它识别 **left 和 right** 的公共 **最左位**。

将公共最左位右边的所有位设置为 0。

使用 **位掩码** 保留公共 **最左位**。

程序

#include <iostream>
#include <climits>
using namespace std;
int sumBitwiseAndInRange(int left, int right) {
    int commonBits = INT_MAX;
    // Continue until left and right have different common leftmost bits
    while ((left & commonBits) != (right & commonBits)) {
        commonBits &= (commonBits - 1);  // Set rightmost bit to 0
    }
    // Perform bitwise AND between left and commonBits to get the final result
    return left & commonBits;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

输出

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

说明

函数 sumBitwiseAndInRange

该函数接受两个整数 **left 和 right**，表示范围。
它将位掩码 commonBits 初始化为 **INT_MAX**，表示所有位都 **设置为 1**。
while 循环持续进行，直到 left 和 right 具有不同的公共最左位（位于最右边不同位左侧的位）。
在每次迭代中，使用 (commonBits - 1) 将 commonBits 的最右位设置为 0。
通过对 left 和 commonBits 执行按位与操作来获得最终结果。

主函数

main 函数演示了 sumBitwiseAndInRange 的用法，使用了一个示例 **范围（left = 5, right = 8）**。
它计算并打印指定范围的按位与和。

复杂度分析

时间复杂度

sumBitwiseAndInRange 函数的时间复杂度主要由 while 循环决定。循环持续进行，直到 **left** 和 **right** 具有不同的公共最左位。在每次迭代中，使用 **(commonBits - 1)** 将 commonBits 的最右位设置为 **0**。此操作需要常数时间。
while 循环中的迭代次数由 left 和 right 的二进制表示中不同的位数决定。因此，时间复杂度为 **O(log(min(left, right)))**。

空间复杂度

空间复杂度非常低且是常数。该算法只使用几个整数变量 **(commonBits, left, right)**，这些变量占用的空间不取决于输入大小。
空间复杂度 **为 O(1)** 或常数。

下一主题C++ 中的 basic_istream::peek() 方法

C++ 中范围内所有子数组按位与和的查询

引言

程序

方法 1：观察规律

程序

方法 2：使用位操作

程序

方法 3：使用按位移位

程序

方法 4：使用公共前缀位掩码

程序

联系信息

关注我们

教程

面试题

在线编译器

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++ 中范围内所有子数组按位与和的查询

引言

程序

方法 1：观察规律

程序

方法 2：使用位操作

程序

方法 3：使用按位移位

程序

方法 4：使用公共前缀位掩码

程序

相关帖子

为使树保持二分图，需要添加的最大边数

C++ 函数重载与函数重写的区别

C++ 初学者书籍

如何在 C++ 中连接两个字符串

C++ std::adjacent_difference

C++ Observer_ptr

C++ forward_list::reverse()

C++ const 关键字

C++ unordered_multimap key_eq 函数

C++ 程序演示浮点输出的格式标志用法