Escriba un programa eficiente para contar el número de 1 en representación binaria de un número entero. Ejemplos:
Input : n = 6 Output : 2 Binary representation of 6 is 110 and has 2 set bits Input : n = 11 Output : 3 Binary representation of 11 is 1101 and has 3 set bits
Tenemos una solución existente para este problema, consulte Count set bits en un enlace entero. Resolveremos este problema en Python utilizando la comprensión de listas . El enfoque es simple,
- Convierta el número dado en su representación binaria usando la función bin (número) .
- Ahora separe todos los 1 de la representación binaria del número dado e imprima la longitud de la lista de 1.
Python3
# Function to count set bits in an integer # in Python def countSetBits(num): # convert given number into binary # output will be like bin(11)=0b1101 binary = bin(num) # now separate out all 1's from binary string # we need to skip starting two characters # of binary string i.e; 0b setBits = [ones for ones in binary[2:] if ones=='1'] print (len(setBits)) # Driver program if __name__ == "__main__": num = 11 countSetBits(num)
Producción:
3
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(log n)
A continuación se muestra una solución de una sola línea.
Python3
num = 11 print (bin(num).count("1"))
Producción
3
Complejidad de tiempo: O (logn)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Shashank Mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA