Flip bits of the sum of count of set bits of two given numbers
Given two numbers A and B, the task is to count the number of set bits in A and B and flip the bits of the obtained sum.
Examples:
Input: A = 5, B = 7
Output: 2
Explanation:
Binary representation of A is 101.
Binary representation of B is 111.
Count of set bits in A and B = 2 + 3 = 5.
Binary representation of the sum obtained = 101
Flipping the bits of the sum, the number obtained is (010)2 = 2.
Therefore, the required output is 2.Input: A = 76, B = 35
Output: 1
Explanation:
Binary representation of A is 1001100
Binary representation of B is 100011
Count of set bits in A and B = 3 + 3 = 6
Binary representation of the sum obtained = 110
Flipping the bits of the sum, the number obtained is (001)2 = 1.
Therefore, the required output is 1.
Naive Approach: The idea to solve this problem is to first traverse through the binary representation of both the numbers and count number of set bits in both the numbers. Finally, add them and invert the bits of the resultant number.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count number of // set bits in integer int countSetBits( int n) { // Variable for counting set bits int count = 0; while (n) { n &= (n - 1); count++; } return count; } // Function to invert bits of a number int invertBits( int n) { // Calculate number of bits of N-1; int x = log2(n); int m = 1 << x; m = m | m - 1; n = n ^ m; return n; } // Function to invert the sum // of set bits in A and B void invertSum( int A, int B) { // Stores sum of set bits int temp = countSetBits(A) + countSetBits(B); cout << invertBits(temp) << endl; } // Driver Code int main() { int A = 5; int B = 7; invertSum(A, B); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count number of // set bits in integer static int countSetBits( int n) { // Variable for counting set bits int count = 0 ; while (n != 0 ) { n &= (n - 1 ); count++; } return count; } // Function to invert bits of a number static int invertBits( int n) { // Calculate number of bits of N-1; int x = ( int )(Math.log(n) / Math.log( 2 )); int m = 1 << x; m = m | m - 1 ; n = n ^ m; return n; } // Function to invert the sum // of set bits in A and B static void invertSum( int A, int B) { // Stores sum of set bits int temp = countSetBits(A) + countSetBits(B); System.out.print(invertBits(temp)); } // Driver Code static public void main(String args[]) { int A = 5 ; int B = 7 ; invertSum(A, B); } } // This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach import math # Function to count number of # set bits in integer def countSetBits(n): # Variable for counting set bits count = 0 while (n ! = 0 ): n & = (n - 1 ) count + = 1 return count # Function to invert bits of a number def invertBits(n): # Calculate number of bits of N-1; x = ( int )(math.log(n) / math.log( 2 )) m = 1 << x m = m | m - 1 n = n ^ m return n # Function to invert the sum # of set bits in A and B def invertSum(A, B): # Stores sum of set bits temp = countSetBits(A) + countSetBits(B) print (invertBits(temp)) # Driver Code A = 5 B = 7 invertSum(A, B) # This code is contributed by shikhasingrajput |
C#
// C# program for the above approach using System; class GFG{ // Function to count number of // set bits in integer static int countSetBits( int n) { // Variable for counting set bits int count = 0; while (n != 0) { n &= (n - 1); count++; } return count; } // Function to invert bits of a number static int invertBits( int n) { // Calculate number of bits of N-1; int x = ( int )Math.Log(n, 2); int m = 1 << x; m = m | m - 1; n = n ^ m; return n; } // Function to invert the sum // of set bits in A and B static void invertSum( int A, int B) { // Stores sum of set bits int temp = countSetBits(A) + countSetBits(B); Console.WriteLine(invertBits(temp)); } // Driver Code static void Main() { int A = 5; int B = 7; invertSum(A, B); } } // This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program for the above approach // Function to count number of // set bits in integer function countSetBits(n) { // Variable for counting set bits var count = 0; while (n != 0) { n &= (n - 1); count++; } return count; } // Function to invert bits of a number function invertBits(n) { // Calculate number of bits of N-1; var x = parseInt((Math.log(n) / Math.log(2))); var m = 1 << x; m = m | m - 1; n = n ^ m; return n; } // Function to invert the sum // of set bits in A and B function invertSum(A, B) { // Stores sum of set bits var temp = countSetBits(A) + countSetBits(B); document.write(invertBits(temp)); } // Driver Code var A = 5; var B = 7; invertSum(A, B); // This code is contributed by Rajput-Ji </script> |
2
Time Complexity: O(logN)
Auxiliary Space: O(1)
Contact Us