Given a positive integer n, count numbers x such that 0 < x <n and x^n > n where ^ is bitwise XOR operation.
Examples:
Input : n = 12 Output : 3 Numbers are 1, 2 and 3 1^12 > 12, 2^12 > 12 and 3^12 > 12 Input : n = 11 Output : 4 Numbers are 4, 5, 6 and 7
A number may x produce a greater XOR value if x has a set bit at a position where n has a 0 bit. So we traverse bits of n, and one by one consider all 0 bits. For every set bit at position k (Considering k = 0 for rightmost bit, k = 1 for second rightmost bit, ..), we add 2 2k to result. For a bit at k-th position, there are 2k numbers with set bit 1.
Below is the implementation of the above idea.
C++
// C++ program to count numbers whose XOR with n// produces a value more than n.#include<bits/stdc++.h>using namespace std;int countNumbers(int n){ /* If there is a number like m = 11110000, then it is bigger than 1110xxxx. x can either 0 or 1. So we have pow(2, k) greater numbers where k is position of rightmost 1 in m. Now by using XOR bit at each position can be changed. To change bit at any position, it needs to XOR it with 1. */ int k = 0; // Position of current bit in n /* Traverse bits from LSB (least significant bit) to MSB */ int count = 0; // Initialize result while (n > 0) { // If current bit is 0, then there are // 2^k numbers with current bit 1 and // whose XOR with n produces greater value if ((n&1) == 0) count += pow(2, k); // Increase position for next bit k += 1; // Reduce n to find next bit n >>= 1; } return count;}// Driver codeint main(){ int n = 11; cout << countNumbers(n) << endl; return 0;} |
Java
// Java program to count numbers// whose XOR with n produces a// value more than n.import java.lang.*;class GFG { static int countNumbers(int n) { // If there is a number like // m = 11110000, then it is // bigger than 1110xxxx. x // can either be 0 or 1. So // where k is the position of // rightmost 1 in m. Now by // using the XOR bit at each // position can be changed. // To change the bit at any // position, it needs to // XOR it with 1. int k = 0; // Position of current bit in n // Traverse bits from LSB (least // significant bit) to MSB int count = 0; // Initialize result while (n > 0) { // If the current bit is 0, then // there are 2^k numbers with // current bit 1 and whose XOR // with n produces greater value if ((n & 1) == 0) count += (int)(Math.pow(2, k)); // Increase position for next bit k += 1; // Reduce n to find next bit n >>= 1; } return count; } // Driver code public static void main(String[] args) { int n = 11; System.out.println(countNumbers(n)); }}// This code is contributed by Smitha. |
Python3
# Python program to count numbers whose # XOR with n produces a value more than n.def countNumbers(n): ''' If there is a number like m = 11110000, then it is bigger than 1110xxxx. x can either 0 or 1. So we have pow(2, k) greater numbers where k is position of rightmost 1 in m. Now by using XOR bit at each position can be changed. To change bit at any position, it needs to XOR it with 1. ''' # Position of current bit in n k = 0 # Traverse bits from # LSB to MSB count = 0 # Initialize result while (n > 0): # If current bit is 0, then there are # 2^k numbers with current bit 1 and # whose XOR with n produces greater value if ((n & 1) == 0): count += pow(2, k) # Increase position for next bit k += 1 # Reduce n to find next bit n >>= 1 return count# Driver coden = 11print(countNumbers(n))# This code is contributed by Anant Agarwal. |
C#
// C# program to count numbers// whose XOR with n produces a// value more than n.using System;class GFG { static int countNumbers(int n) { // If there is a number like // m = 11110000, then it is // bigger than 1110xxxx. x // can either be 0 or 1. So // where k is the position of // rightmost 1 in m. Now by // using the XOR bit at each // position can be changed. // To change the bit at any // position, it needs to // XOR it with 1. int k = 0; // Position of current bit in n // Traverse bits from LSB (least // significant bit) to MSB int count = 0; // Initialize result while (n > 0) { // If the current bit is 0, then // there are 2^k numbers with // current bit 1 and whose XOR // with n produces greater value if ((n & 1) == 0) count += (int)(Math.Pow(2, k)); // Increase position for next bit k += 1; // Reduce n to find next bit n >>= 1; } return count; } // Driver code public static void Main() { int n = 11; Console.WriteLine(countNumbers(n)); }}// This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program to count // numbers whose XOR with n// produces a value more than n.function countNumbers($n){ /* If there is a number like m = 11110000, then it is bigger than 1110xxxx. x can either 0 or 1. So we have pow(2, k) greater numbers where k is position of rightmost 1 in m. Now by using XOR bit at each position can be changed. To change bit at any position, it needs to XOR it with 1. */ // Position of current bit in n $k = 0; /* Traverse bits from LSB (least significant bit) to MSB */ // Initialize result $count = 0; while ($n > 0) { // If current bit is 0, // then there are 2^k // numbers with current // bit 1 and whose XOR // with n produces greater // value if (($n & 1) == 0) $count += pow(2, $k); // Increase position // for next bit $k += 1; // Reduce n to // find next bit $n >>= 1; } return $count;} // Driver code $n = 11; echo countNumbers($n);// This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to count numbers whose XOR with n// produces a value more than n. function countNumbers(n) { // If there is a number like // m = 11110000, then it is // bigger than 1110xxxx. x // can either be 0 or 1. So // where k is the position of // rightmost 1 in m. Now by // using the XOR bit at each // position can be changed. // To change the bit at any // position, it needs to // XOR it with 1. let k = 0; // Position of current bit in n // Traverse bits from LSB (least // significant bit) to MSB let count = 0; // Initialize result while (n > 0) { // If the current bit is 0, then // there are 2^k numbers with // current bit 1 and whose XOR // with n produces greater value if ((n & 1) == 0) count += (Math.pow(2, k)); // Increase position for next bit k += 1; // Reduce n to find next bit n >>= 1; } return count; }// Driver Code let n = 11; document.write(countNumbers(n)); </script> |
Output:
4
Time complexity: O(logn)
Auxiliary Space: O(1)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
