Dado un entero positivo n, cuente números x tales que 0 < x <n y x^n > n donde ^ es una operación XOR bit a bit.
Ejemplos:
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
Un número puede x producir un valor XOR mayor si x tiene un bit establecido en una posición donde n tiene un bit 0. Así que recorremos bits de n, y uno por uno consideramos todos los bits 0. Para cada bit establecido en la posición k (Considerando k = 0 para el bit más a la derecha, k = 1 para el segundo bit más a la derecha, ..), sumamos 2 2 k al resultado. Para un bit en la k-ésima posición, hay 2 k números con el bit 1 establecido.
A continuación se muestra la implementación de la idea anterior.
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 code
int 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 code n = 11 print(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>
Producción:
4
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Smarak Chopdar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA