Skip to content

Instantly share code, notes, and snippets.

@pknowledge
Created June 22, 2020 15:08
Show Gist options
  • Save pknowledge/8021d512ac9b967f24c8bff63fbd831e to your computer and use it in GitHub Desktop.
Save pknowledge/8021d512ac9b967f24c8bff63fbd831e to your computer and use it in GitHub Desktop.
Competitive Programming with Python-Bit Magic- Power of 2 + One's in Binary Representation of Number https://youtu.be/SdP4j-n8S0g
# ispowerof 2
# n -> input
# True/False -> output
# check if n is a powerof 2
# 512 -> True 512 = 2**9
# 1024 -> True 1024 = 2**10
def ispowerof2(n):
# T.C = O(1)
if n <= 0:
return False
x = n
y = not(n & (n-1))
return x and y
# return's number of 1's in binary representation of int
# 5 -> 101 ans = 2
# 7 -> 111 ans = 3
def bruteforcecntbits(n):
# T.C = O(n)
s = str(bin(n))[2:]
print("{}".format(s))
return s.count('1')
def cntbits(n):
# T.C = O(logn)
cnt = 0
while n:
cnt+=1
n = n & (n-1)
return cnt
t= int(input())
while t:
n = int(input())
#print(ispowerof2(n))
print(bruteforcecntbits(n))
print(cntbits(n))
t=t-1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment