Dado un entero X. La tarea es encontrar el número positivo más pequeño Y (> 0) tal que X AND Y sea cero .
Ejemplos:
Entrada: X = 3
Salida: 4
4 es el número positivo más pequeño cuyo AND bit a bit con 3 es cero
Entrada: X = 10
Salida: 1
Enfoque :
Hay 2 casos :
- Si la representación binaria de X contiene todos 1, en ese caso, todos los bits de Y deben ser 0 para que el resultado de la operación AND sea cero. Entonces X+1 es nuestra respuesta, que es el primer entero positivo.
- Si la representación binaria de X no contiene todos los 1, en ese caso, encuentre la primera posición en X en la que el bit es 0 . Entonces nuestra respuesta será potencia(2, posición)
A continuación se muestra la implementación del enfoque anterior:
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 1000000007
using namespace std;
// Method to find smallest number Y for
// a given value of X such that X AND Y is zero
int 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 Code
int 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 zero
import 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 zero
def 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 Code
if __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 zero
using 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 zero
function 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 code
let X = findSmallestNonZeroY(10);
document.write(X);
// This code is contributed by unknown2108
</script>
Producción:
1
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)