Dado un número n, la tarea es verificar si este número es un múltiplo de 4 o no sin usar los operadores +, -, * y %.
Ejemplos:
Input: n = 4 Output - Yes
n = 20 Output - Yes
n = 19 Output - No
Método 1 (usando XOR)
Un hecho interesante para n > 1 es que hacemos XOR de todos los números del 1 al n y si el resultado es igual a n, entonces n es un múltiplo de 4, de lo contrario no lo es.
C++
// An interesting XOR based method to check if
// a number is multiple of 4.
#include<bits/stdc++.h>
using namespace std;
// Returns true if n is a multiple of 4.
bool isMultipleOf4(int n)
{
if (n == 1)
return false;
// Find XOR of all numbers from 1 to n
int XOR = 0;
for (int i = 1; i <= n; i++)
XOR = XOR ^ i;
// If XOR is equal n, then return true
return (XOR == n);
}
// Driver code to print multiples of 4
int main()
{
// Printing multiples of 4 using above method
for (int n=0; n<=42; n++)
if (isMultipleOf4(n))
cout << n << " ";
return 0;
}
Java
// An interesting XOR based method to check if
// a number is multiple of 4.
class Test
{
// Returns true if n is a multiple of 4.
static boolean isMultipleOf4(int n)
{
if (n == 1)
return false;
// Find XOR of all numbers from 1 to n
int XOR = 0;
for (int i = 1; i <= n; i++)
XOR = XOR ^ i;
// If XOR is equal n, then return true
return (XOR == n);
}
// Driver method
public static void main(String[] args)
{
// Printing multiples of 4 using above method
for (int n=0; n<=42; n++)
System.out.print(isMultipleOf4(n) ? n : " ");
}
}
Python 3
# An interesting XOR based # method to check if a # number is multiple of 4. # Returns true if n is a # multiple of 4. def isMultipleOf4(n): if (n == 1): return False # Find XOR of all numbers # from 1 to n XOR = 0 for i in range(1, n + 1): XOR = XOR ^ i # If XOR is equal n, then # return true return (XOR == n) # Driver code to print # multiples of 4 Printing # multiples of 4 using # above method for n in range(0, 43): if (isMultipleOf4(n)): print(n, end = " ") # This code is contributed # by Smitha
C#
// An interesting XOR based method
// to check if a number is multiple
// of 4.
using System;
class GFG {
// Returns true if n is a
// multiple of 4.
static bool isMultipleOf4(int n)
{
if (n == 1)
return false;
// Find XOR of all numbers
// from 1 to n
int XOR = 0;
for (int i = 1; i <= n; i++)
XOR = XOR ^ i;
// If XOR is equal n, then
// return true
return (XOR == n);
}
// Driver method
public static void Main()
{
// Printing multiples of 4
// using above method
for (int n = 0; n <= 42; n++)
{
if (isMultipleOf4(n))
Console.Write(n+" ");
}
}
}
// This code is contributed by Smitha.
PHP
<?php
// PHP program to check if
// a number is multiple of 4.
// Returns true if n is
// a multiple of 4.
function isMultipleOf4($n)
{
if ($n == 1)
return false;
// Find XOR of all
// numbers from 1 to n
$XOR = 0;
for ($i = 1; $i <= $n; $i++)
$XOR = $XOR ^ $i;
// If XOR is equal n,
// then return true
return ($XOR == $n);
}
// Driver Code
// Printing multiples of 4
// using above method
for ($n = 0; $n <= 42; $n++)
if (isMultipleOf4($n))
echo $n, " ";
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript program of interesting XOR based method to check if
// a number is multiple of 4.
// Returns true if n is a multiple of 4.
function isMultipleOf4(n)
{
if (n == 1)
return false;
// Find XOR of all numbers from 1 to n
let XOR = 0;
for (let i = 1; i <= n; i++)
XOR = XOR ^ i;
// If XOR is equal n, then return true
return (XOR == n);
}
// Driver Code
// Printing multiples of 4 using above method
for (let n = 0; n <= 42; n++)
document.write(isMultipleOf4(n) ? n : " ");
// This code is contributed by avijitmondal1998.
</script>
Producción :
0 4 8 12 16 20 24 28 32 36 40
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
¿Como funciona esto?
Cuando hacemos XOR de números, obtenemos 0 como valor XOR justo antes de un múltiplo de 4. Esto sigue repitiéndose antes de cada múltiplo de 4.
Number Binary-Repr XOR-from-1-to-n 1 1 [0001] 2 10 [0011] 3 11 [0000]
Método 2 (usando operadores de desplazamiento bit a bit)
La idea es eliminar los últimos dos bits usando >>, luego multiplicar por 4 usando <<. Si el resultado final es igual a n, entonces los últimos dos bits fueron 0, por lo que el número fue un múltiplo de cuatro.
C++
// An interesting XOR based method to check if
// a number is multiple of 4.
#include<bits/stdc++.h>
using namespace std;
// Returns true if n is a multiple of 4.
bool isMultipleOf4(long long n)
{
if (n==0)
return true;
return (((n>>2)<<2) == n);
}
// Driver code to print multiples of 4
int main()
{
// Printing multiples of 4 using above method
for (int n=0; n<=42; n++)
if (isMultipleOf4(n))
cout << n << " ";
return 0;
}
Java
// An interesting XOR based method to check if
// a number is multiple of 4.
class Test
{
// Returns true if n is a multiple of 4.
static boolean isMultipleOf4(long n)
{
if (n==0)
return true;
return (((n>>2)<<2) == n);
}
// Driver method
public static void main(String[] args)
{
// Printing multiples of 4 using above method
for (int n=0; n<=42; n++)
System.out.print(isMultipleOf4(n) ? n : " ");
}
}
Python3
# Python3 code to implement an interesting XOR # based method to check if a number is multiple of 4. # Returns true if n is a multiple of 4. def isMultipleOf4(n): if (n == 0): return True return (((n>>2)<<2) == n) # Driver code to print multiples of 4 #Printing multiples of 4 using above method for n in range(43): if isMultipleOf4(n): print(n, end = " ") # This codeis contributed by phasing17
C#
// An interesting XOR based method to
// check if a number is multiple of 4.
using System;
class GFG {
// Returns true if n is a multiple
// of 4.
static bool isMultipleOf4(int n)
{
if (n == 0)
return true;
return (((n >> 2) << 2) == n);
}
// Driver code to print multiples
// of 4
static void Main()
{
// Printing multiples of 4 using
// above method
for (int n = 0; n <= 42; n++)
if (isMultipleOf4(n))
Console.Write(n + " ");
}
}
// This code is contributed by Anuj_67
PHP
<?php
// PHP program to check if
// a number is multiple of 4.
// Returns true if n is
// a multiple of 4.
function isMultipleOf4($n)
{
if ($n == 0)
return true;
return ((($n >> 2) << 2) == $n);
}
// Driver Code
// Printing multiples of 4
// using above method
for ($n = 0; $n <= 42; $n++)
if (isMultipleOf4($n))
echo $n , " ";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// An interesting XOR based method to
// check if a number is multiple of 4.
// Returns true if n is a multiple
// of 4.
function isMultipleOf4(n)
{
if (n == 0)
return true;
return (((n >> 2) << 2) == n);
}
// Printing multiples of 4 using
// above method
for (let n = 0; n <= 42; n++)
if (isMultipleOf4(n))
document.write(n + " ");
</script>
Producción :
0 4 8 12 16 20 24 28 32 36 40
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Como podemos ver, la idea principal para encontrar la multiplicidad de 4 es verificar los menos dos bits significativos del número dado. Sabemos que para cualquier número par, el bit menos significativo siempre es CERO (es decir, 0). De manera similar, para cualquier número que sea múltiplo de 4 tendrá al menos dos bits significativos como CERO. Y con la misma lógica, para que cualquier número sea múltiplo de 8, al menos tres bits significativos serán CERO. Es por eso que podemos usar el operador AND (&) también con otro operando como 0x3 para encontrar la multiplicidad de 4.
Este artículo es una contribución de Sahil Chhabra (KILLER) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su 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