Given an integer X. The task is to find the smallest positive number Y(> 0) such that X AND Y is zero.
Examples:
Input : X = 3
Output : 4
4 is the smallest positive number whose bitwise AND with 3 is zero
Input : X = 10
Output : 1
Approach :
There are 2 cases :
- If the binary representation of X contains all 1s, in that case, all the bits of Y should be 0 to make the result of AND operation is zero. Then X+1 is our answer which is the first positive integer.
- If the binary representation of X doesn’t contain all 1s, in that case, find the first position in X at which bit is 0. Then our answer will be power(2, position)
Below is the implementation of the above approach :
C++
// C++ program to find smallest number Y for// a given value of X such that X AND Y is zero#include <bits/stdc++.h>#define mod 1000000007using namespace std;// Method to find smallest number Y for// a given value of X such that X AND Y is zeroint findSmallestNonZeroY(int A_num){ // Convert the number into its binary form string A_binary = bitset<8>(A_num).to_string(); int B = 1; int length = A_binary.size(); int no_ones = __builtin_popcount(A_num); // Case 1 : If all bits are ones, // then return the next number if (length == no_ones ) return A_num + 1; // Case 2 : find the first 0-bit // index and return the Y for (int i=0;i<length;i++) { char ch = A_binary[length - i - 1]; if (ch == '0') { B = pow(2.0, i); break; } } return B;}// Driver Codeint main(){ int X = findSmallestNonZeroY(10); cout << X;}// This code is contributed by mohit kumar 29 |
Java
// Java program to find smallest number Y for // a given value of X such that X AND Y is zeroimport java.lang.*;public class Main { // Method to find smallest number Y for // a given value of X such that X AND Y is zero static long findSmallestNonZeroY(long A_num) { // Convert the number into its binary form String A_binary = Long.toBinaryString(A_num); long B = 1; int len = A_binary.length(); int no_ones = Long.bitCount(A_num); // Case 1 : If all bits are ones, // then return the next number if (len == no_ones) { return A_num + 1; } // Case 2 : find the first 0-bit // index and return the Y for (int i = 0; i < len; i++) { char ch = A_binary.charAt(len - i - 1); if (ch == '0') { B = (long)Math.pow(2.0, (double)i); break; } } return B; } // Driver code public static void main(String[] args) { long X = findSmallestNonZeroY(10); System.out.println(X); }} |
Python3
# Python3 program to find smallest number Y for # a given value of X such that X AND Y is zero# Method to find smallest number Y for # a given value of X such that X AND Y is zerodef findSmallestNonZeroY(A_num) : # Convert the number into its binary form A_binary = bin(A_num) B = 1 length = len(A_binary); no_ones = (A_binary).count('1'); # Case 1 : If all bits are ones, # then return the next number if length == no_ones : return A_num + 1; # Case 2 : find the first 0-bit # index and return the Y for i in range(length) : ch = A_binary[length - i - 1]; if (ch == '0') : B = pow(2.0, i); break; return B; # Driver Codeif __name__ == "__main__" : X = findSmallestNonZeroY(10); print(X) # This code is contributed by AnkitRai01 |
C#
// C# program to find smallest number Y for // a given value of X such that X AND Y is zerousing System; class GFG { // Method to find smallest number Y for // a given value of X such that X AND Y is zero static long findSmallestNonZeroY(long A_num) { // Convert the number into its binary form String A_binary = Convert.ToString(A_num, 2); long B = 1; int len = A_binary.Length; int no_ones = bitCount(A_num); // Case 1 : If all bits are ones, // then return the next number if (len == no_ones) { return A_num + 1; } // Case 2 : find the first 0-bit // index and return the Y for (int i = 0; i < len; i++) { char ch = A_binary[len - i - 1]; if (ch == '0') { B = (long)Math.Pow(2.0, (double)i); break; } } return B; } static int bitCount(long x) { // To store the count // of set bits int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits; } // Driver code public static void Main(String[] args) { long X = findSmallestNonZeroY(10); Console.WriteLine(X); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find smallest number Y for // a given value of X such that X AND Y is zero// Method to find smallest number Y for // a given value of X such that X AND Y is zerofunction findSmallestNonZeroY(A_num){ // Convert the number into its binary form let A_binary = (A_num >>> 0).toString(2); let B = 1; let len = A_binary.length; let no_ones = bitCount(A_num); // Case 1 : If all bits are ones, // then return the next number if (len == no_ones) { return A_num + 1; } // Case 2 : find the first 0-bit // index and return the Y for (let i = 0; i < len; i++) { let ch = A_binary[len - i - 1]; if (ch == '0') { B = Math.floor(Math.pow(2.0, i)); break; } } return B;}function bitCount(x){ // To store the count // of set bits let setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;}// Driver codelet X = findSmallestNonZeroY(10);document.write(X);// This code is contributed by unknown2108</script> |
Output:
1
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/find-smallest-positive-number-y-such-that-bitwise-and-of-x-and-y-is-zero/ […]
… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/find-smallest-positive-number-y-such-that-bitwise-and-of-x-and-y-is-zero/ […]