Count set bits in Bitwise XOR of all adjacent elements upto N

0 0 4 minutes read

Given a positive integer N, the task is to find the total count of set bits by performing Bitwise XOR on all possible adjacent elements in the range [0, N].

Examples:

Input: N = 4
Output: 7
Explanation:
Bitwise XOR of 0 and 1 = 001 and count of set bits = 1
Bitwise XOR of 1 and 2 = 011 and count of set bits = 2
Bitwise XOR of 2 and 3 = 001 and count of set bits = 1
Bitwise XOR of 3 and 4 = 111 and count of set bits = 3
Therefore, the total count of set bits by performing the XOR operation on all possible adjacent elements of the range [0, N] = (1 + 2 + 1 + 3) = 7

Input: N = 7
Output: 11

Naive Approach: The simplest approach to solve this problem is to iterate over the range [0, N] and count all possible set bits by performing Bitwise XOR on each adjacent element over the range [0, N]. Finally, print the total count of all possible set bits.

Time Complexity: O(N * log₂N)
Auxiliary Space: O(1)

Efficient approach: To optimize the above approach, the idea is based on the following observations:

If the position of the rightmost set bit of X is K, then the count of set bits in (X ^ (X – 1)) must be K.

Follow the steps below to solve the problem:

Initialize a variable, say bit_position to store all possible values of the right most bit over the range [0, N].
Initialize a variable, say total_set_bits to store the sum of all possible set bits by performing the Bitwise XOR operation on all possible adjacent elements over the range [0, N].
Iterate over the range [0, N] and Update N = N – (N + 1) / 2 and total_set_bits += ((N + 1) / 2 * bit_position).
Finally, print the value of total_set_bits.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
int countXORSetBitsAdjElemRange1_N(int N)
{
 
    // Stores count of set bits by Bitwise
    // XOR on adjacent elements of [0, N]
    int total_set_bits = 0;
 
    // Stores all possible values on
    // right most set bit over [0, N]
    int bit_Position = 1;
 
    // Iterate over the range [0, N]
    while (N) {
        total_set_bits += ((N + 1) / 2
                           * bit_Position);
 
        // Update N
        N -= (N + 1) / 2;
 
        // Update bit_Position
        bit_Position++;
    }
 
    return total_set_bits;
}
 
// Driver Code
int main()
{
    int N = 4;
 
    cout << countXORSetBitsAdjElemRange1_N(N);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
   
class GFG{
   
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
static int countXORSetBitsAdjElemRange1_N(int N)
{
     
    // Stores count of set bits by Bitwise
    // XOR on adjacent elements of [0, N]
    int total_set_bits = 0;
  
    // Stores all possible values on
    // right most set bit over [0, N]
    int bit_Position = 1;
  
    // Iterate over the range [0, N]
    while (N != 0) 
    {
        total_set_bits += ((N + 1) / 2 * 
                           bit_Position);
  
        // Update N
        N -= (N + 1) / 2;
  
        // Update bit_Position
        bit_Position++;
    }
    return total_set_bits;
}
   
// Driver Code
public static void main(String[] args)
{
    int N = 4;
  
    System.out.println(countXORSetBitsAdjElemRange1_N(N));
}
}
   
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program to implement
# the above approach
 
# Function to count of set bits in Bitwise
# XOR of adjacent elements up to N
def countXORSetBitsAdjElemRange1_N(N):
     
    # Stores count of set bits by Bitwise
    # XOR on adjacent elements of [0, N]
    total_set_bits = 0
 
    # Stores all possible values on
    # right most set bit over [0, N]
    bit_Position = 1
 
    # Iterate over the range [0, N]
    while (N):
        total_set_bits += ((N + 1) //
                            2 * bit_Position)
                             
        # Update N
        N -= (N + 1) // 2
 
        # Update bit_Position
        bit_Position += 1
 
    return total_set_bits
 
# Driver Code
if __name__ == '__main__':
     
    N = 4
     
    print(countXORSetBitsAdjElemRange1_N(N))
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program to implement
// the above approach  
using System;
    
class GFG{
     
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
static int countXORSetBitsAdjElemRange1_N(int N)
{
     
    // Stores count of set bits by Bitwise
    // XOR on adjacent elements of [0, N]
    int total_set_bits = 0;
   
    // Stores all possible values on
    // right most set bit over [0, N]
    int bit_Position = 1;
   
    // Iterate over the range [0, N]
    while (N != 0) 
    {
        total_set_bits += ((N + 1) / 2 * 
                           bit_Position);
   
        // Update N
        N -= (N + 1) / 2;
   
        // Update bit_Position
        bit_Position++;
    }
    return total_set_bits;
}
  
// Driver Code
public static void Main()
{
    int N = 4;
   
    Console.Write(countXORSetBitsAdjElemRange1_N(N));
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
// Javascript program to implement
// the above approach
 
 
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
function countXORSetBitsAdjElemRange1_N(N)
{
 
    // Stores count of set bits by Bitwise
    // XOR on adjacent elements of [0, N]
    let total_set_bits = 0;
 
    // Stores all possible values on
    // right most set bit over [0, N]
    let bit_Position = 1;
 
    // Iterate over the range [0, N]
    while (N) {
        total_set_bits += (Math.floor((N + 1) / 2) * bit_Position);
 
        // Update N
        N -= Math.floor((N + 1) / 2);
 
        // Update bit_Position
        bit_Position++;
    }
 
    return total_set_bits;
}
 
// Driver Code
let N = 4;
 
document.write(countXORSetBitsAdjElemRange1_N(N));
 
 
// This code is contributed by _saurabh_jaiswal
</script>

Output:

Time complexity:O(Log₂N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!