# Bitwise AND sumBitwise AND sum solution

Problem

You are given an array $�$ consisting of $�$ positive integers. Here, $�\left(�,�\right)$ is defined as the bitwise AND of all elements of the array $�$ after replacing all elements of $�$ in range $\left[�,�\right]$ (both inclusive) with $\left({2}^{25}-1\right)$. Your task is to find:
$-�\left(1,�\right)+\sum _{�=1}^{�}\sum _{�=�}^{�}�\left(�,�\right)$

Note that after calculating the value $�\left(�,�\right)$ for some $\left(�,�\right)$, the array is restored back to its original form. Therefore, calculating $�\left(�,�\right)$ for each $\left(�,�\right)$ pair is independent.

You are given $�$ test cases.

Warning: Use FAST I/O Methods.

Input format

• The first line contains a single integer $�$ denoting number of test cases.
• For each test case:
• The first line contains a single integer $�$ denoting the length of the array.
• The second line contains $�$ space-separated integers denoting the integer array $�$.

Output format

For each test case, print the required sum in a separate line.

Constraints

Sample Input
2
3
3 4 1
2
4 2

Sample Output
5
6

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Consider the first test case, $�=3$$�=\left[3,4,1\right]$. We want to evaluate $�\left(1,1\right)+�\left(1,2\right)+�\left(2,2\right)+�\left(2,3\right)+�\left(3,3\right)$. Calculations are shown below:

• $�\left(1,1\right)$ : Replace ${�}_{1}$ with $\left({2}^{25}-1\right)$, we get $�=\left[33554431,4,1\right]$, Bitwise AND of elements is 0.
• $�\left(1,2\right)$ : Replace ${�}_{1},{�}_{2}$ with $\left({2}^{25}-1\right)$, we get $�=\left[33554431,33554431,1\right]$, Bitwise AND of elements is 1.
• $�\left(2,2\right)$ : Replace ${�}_{2}$ with $\left({2}^{25}-1\right)$, we get $�=\left[3,33554431,1\right]$, Bitwise AND of elements is 1.
• $�\left(2,3\right)$ : Replace ${�}_{2},{�}_{3}$ with $\left({2}^{25}-1\right)$, we get $�=\left[3,33554431,33554431\right]$, Bitwise AND of elements is 3.
• $�\left(3,3\right)$ : Replace ${�}_{3}$ with $\left({2}^{25}-1\right)$, we get $�=\left[3,4,33554431\right]$, Bitwise AND of elements is 0.
• The sum is $0+1+1+3+0=5$.

Consider the second test case, $�=2$$�=\left[4,2\right]$. We want to evaluate $�\left(1,1\right)+�\left(2,2\right)$. Calculations are shown below:

• $�\left(1,1\right)$ : Replace ${�}_{1}$ with $\left({2}^{25}-1\right)$, we get $�=\left[33554431,2\right]$, Bitwise AND of elements is 2.
• $�\left(2,2\right)$ : Replace ${�}_{2}$ with $\left({2}^{25}-1\right)$, we get $�=\left[4,33554431\right]$, Bitwise AND of elements is 4.
• The sum is $2+4=6$.

## Bitwise AND sumBitwise AND sum Solution(C++):-

#include <iostream>
#include <vector>
#include <cstdint>
uint64_t bwand_sum(const std::vector<uint32_t> &v) {
constexpr uint32_t mask = (1 << 25) - 1;
const auto n = static_cast<int>(v.size());
int i, j;
std::vector<uint32_t> left_and(n + 1);
for (i = 0; i < n; i++) {
left_and[i + 1] = v[i] & left_and[i];
}
std::vector<uint32_t> right_and(n);
for (i = n - 2; i >= 0; i--) {
right_and[i] = v[i + 1] & right_and[i + 1];
}
std::vector<int> ranges;
i = 0;
ranges.push_back(i);
while (i < n) {
for (j = i + 1;
j < n && left_and[i] == left_and[j] && right_and[i] == right_and[j];
j++) { }
i = j;
ranges.push_back(i);
}
const auto m = ranges.size();
uint64_t sum = 0u;
for (i = 0; i < m - 1; i++) {
const uint64_t len_i = ranges[i + 1] - ranges[i];
const uint64_t subrange_count_self = ((len_i + 1) * len_i) >> 1;
sum += subrange_count_self * static_cast<uint64_t>(left_and[ranges[i]] & right_and[ranges[i]]);
for (j = i + 1; j < m - 1; j++) {
const uint64_t len_j = ranges[j + 1] - ranges[j];
const uint64_t combined_range_count = len_i * len_j;
sum += combined_range_count * static_cast<uint64_t>(left_and[ranges[i]] & right_and[ranges[j]]);
}
}
}
int main(int argc, char **argv) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
while (t-- > 0) {
int n;
std::cin >> n;
std::vector<uint32_t> v(n);
for (auto i = 0; i < n; i++) {
std::cin >> v[i];
}
std::cout << bwand_sum(v) << '\n';
}
return 0;
}