Mayor potencia de dos que divide a un número dado

Dado un número n, encuentra la mayor potencia de 2 que divide a n.
Ejemplos:
 

Entrada: n = 48 
Salida: 16 
La potencia más alta de 2 que divide a 48 es 16.
Entrada: n = 5 
Salida: 1 
La potencia más alta de 2 que divide a 5 es 1.

Una solución simple es probar todas las potencias de 2 una por una comenzando desde 1, luego 2, luego 4 y así sucesivamente.
Una solución eficiente se basa en la magia de bits . Si observamos más de cerca, podemos notar que, básicamente, necesitamos encontrar el número que tiene el bit más a la derecha establecido en la misma posición que n y todos los demás bits en 0. Por ejemplo, para n = 5 (10 1 ), nuestra salida es 00 1 . Para n = 48 (1 1 0000), nuestra salida es 0 1 0000 
¿Cómo encontramos un número que tiene el mismo bit establecido más a la derecha y todos los demás bits como 0?  
Seguimos los pasos a continuación.
Sea n = 48 (00110000) Restamos 
uno de n, es decir, hacemos n-1 . Obtenemos 47(00101111) 
Haz la negación de (n-1), es decir, hacemos ~(n-1) . Obtenemos (11010000). 
Do n & (~(n-1)) , obtenemos 00010000 que tiene un valor de 16.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find highest power
// of 2 that divides n.
#include<iostream>
using namespace std;
 
int highestPowerOf2(int n)
{
    return (n & (~(n - 1)));
}
 
int main()
{
    int n = 48;
    cout << highestPowerOf2(n);
    return 0;
}

// Java program to find highest power
// of 2 that divides n.
  
class GFG
{
      
static int highestPowerOf2(int n)
{
    return (n & (~(n - 1)));
}
  
public static void main(String []args)
{
    int n = 48;
    System.out.println(highestPowerOf2(n));
}
}

# Python3 program to find highest power
# of 2 that divides n.
 
def highestPowerOf2(n):
 
    return (n & (~(n - 1)))
 
 
#Driver code
if __name__=='__main__':
    n = 48
    print(highestPowerOf2(n))
 
# this code is contributed
# by ash264

// C# program to find highest power
// of 2 that divides n.
using System;
 
class GFG
{
     
static int highestPowerOf2(int n)
{
    return (n & (~(n - 1)));
}
 
public static void Main()
{
    int n = 48;
    Console.Write(highestPowerOf2(n));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<?php
// PHP program to find highest power
// of 2 that divides n.
 
function highestPowerOf2($n)
{
    return ($n & (~($n - 1)));
}
 
// Driver Code
$n = 48;
echo highestPowerOf2($n);
 
// This code is contributed
// by Sach_Code..
?>

<script>
 
// javascript program to find highest power
// of 2 that divides n.
  
 
      
function highestPowerOf2(n)
{
    return (n & (~(n - 1)));
}
 
var n = 48;
document.write(highestPowerOf2(n));
 
 
// This code is contributed by 29AjayKumar
 
</script>

16

Complejidad de tiempo: O(log ₂ n)
Complejidad de espacio:- O(1).

Enfoque – 2: este también es un enfoque eficiente, donde puede encontrar el divisor más grande de la potencia dos para un número ‘n’ usando una función predefinida en C para manejar bits. Que es  _builtin_ctz(n) , esta función lo ayuda a encontrar los ceros finales del número, y luego puede ver la magia de los bits.

Entrada: n = 48 ~= (110000) ₂     // el número de ceros finales es = 4, por lo que el número de ceros finales = 4

Salida: 1<<4 =16 // pow(2,4) = 16 La potencia más alta de 2 que divide a 48 es 16.

Entrada: n = 21 ~= (10101) ₂        // no hay ceros finales presentes, por lo que el número de ceros finales = 0

Salida: 1<<0 =2 // potencia(2,0)=1

Nota: Para conocer en detalle estas funciones de enmascaramiento de bits, puede leer este artículo.

#include <stdio.h>
int main()
{
    int n = 21;     
    int m = 48;
    printf("for %d is %d ",
           n,(1<< __builtin_ctz(n)));
    printf("\nfor %d is %d ",
           m,(1<< __builtin_ctz(m)));
    return 0;
}

for 21 is 1 
for 48 is 16 

Complejidad de tiempo: O(log ₂ n)
Complejidad de espacio: O(1)