LeetCode 191(Number of 1 Bits, Python)

1. 문제 링크

• Number of 1 Bits - LeetCode

Number of 1 Bits - LeetCode

2. 문제 설명

• 10진법 수가 입력되었을 때 이를 32bit로 표현했을 때 1의 개수를 반환하는 문제
• 예시) 11이 입력되면 00000000000000000000000000001011에서 1의 개수인 3을 반환

3. 처음 풀이

• 27ms(98.49%), 16.17mb(61.167%)
• n입력시 bin(n)을 이용하여 2진법으로 바꾸고 for문을 이용하여 1이면 result 값을 1씩 증가

class Solution:
    def hammingWeight(self, n: int) -> int:
        result = 0
        for i in bin(n):
            if i == '1':
                result += 1
        return result

4. 다른 풀이

• 비트 연산을 적극적으로 활용
• n>>i 연산을 통해 1bit씩 우측 시프트한 후
• &1 연산을 통해 가장 오른쪽이 1이면 res를 1씩 증가

class Solution:
    def hammingWeight(self, n: int) -> int:
        res=0
        for i in range(32):
            res+=(n>>i)&1 #우측 i번째가 1이면 res 1증가
        return res

---

• 수학적으로 2로 나눈 나머지가 1이면 2진법에서 1, 0이면 0이 됨을 이용하여 2로 나누는 것을 반복하여 그 나머지를 누적하여 결과에 더함

class Solution:
    def hammingWeight(self, n: int) -> int:
        o = 0 #결과
        while n > 0:
            o += n % 2 #2로 나눈 나머지 더함
            n = n // 2 #2로 나눈 몫으로 업데이트
        return o

---

• “{0:b}”.format(n)을 이용하여 2진법 문자열 string으로 바꾼 후
• map(int, string)을 이용하여 각각을 정수로 바꾼 list를 생성
• sum 통해서 list의 모든 원소를 더하여 반환

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum(map(int, "{0:b}".format(n)))

5. 배운 점

• 비트 연산, format(), map함수 모두 익숙해져서 자유롭게 쓰도록 하자.

---

• bit 연산자 >>, <<
  • >>(Right Shift), 오른쪽 시프트 연산자
  • a>>b는 a의 비트를 오른쪽으로 b만큼 이동시킴
  • <<(Left Shift), 왼쪽 시프트 연산자는 반대로 a의 비트를 왼쪽으로 b만큼 이동시킴
  • 유의할 점
    • 결과 값의 범위 밖으로 넘치는 비트는 소멸, 새로운 비트는 0으로 채워짐
    • 결과 값의 크기는 피연산자의 타입에 의해 결정
    • 곱하거나 나누기 연산 보다 >>, <<의 연산이 훨씬 빠름
    • 소멸되는 비트가 없다면 <<를 한 칸할 때마다 결과값은 2배, >>를 한칸할 때마다 (소수 발생하기 전까진) 절반이 됨(2진법 생각하면 당연)
    • 피연산자의 부호에 유의, int나 long의 경우 최상위 비트가 1이면 음수를 뜻함. 최상위 비트인 경우 >> 연산하면 최상위 비트는 1로 채워짐.(음수로 유지)

a = -8 #1111 0111(8bit, 1의 보수 방식)
result = a >> 2 #1111 1101
print(result)#

 

• bit 연산자 &(AND), |(OR), ^(XOR) ~(NOT)
  • &는 A, B 모두 1이면 1
  • |는 A, B 중 하나라도 1이면 1
  • ^은 A, B 중 하나만 1이면 즉 서로 다르면 1
  • ~은 반전으로 A가 1이면 0, 0이면 1

---

• 2진수의 음수 표현법
  • 최상위 비트를 부호로 사용하고 뒤는 그대로 사용하는 경우
    • 장점 : 사람이 보기에 직관적임
    • 단점 : 연산을 할 때 최상위 비트와 절댓값의 대소 관계를 따져주어야하여 복잡함.
  • 1의 보수 방식
    • 장점 : 원래 비트를 반전만 하면 됨, 뺼셈이 간단함.
    • 단점 : 최상위 비트 넘어선 올림(캐리) 발생시 1을 더해주어야함. +0과 -0을 모두 인지할 수 있도록 처리해야함.
  • 2의 보수 방식
    • 1의 보수 방식에서 +0, -0 문제를 해결
    • 부호를 바꾸려면 비트를 반전 후 1을 더하면 됨
    • 대부분 컴퓨터에서 사용하는 방식

---

• 2진법 변환 방법1. bin() 함수 이용

decimal_number = 10
binary_representation = bin(decimal_number)
print(binary_representation)  # 출력 결과: 0b1010, 0b는 진법 표시

decimal_number = 10
binary_representation = bin(decimal_number)[2:] #[2:]를 이용하여 진법 표시 삭제
print(binary_representation)  # 출력 결과: 1010

 

• 2진법 변환 방법2. format() 메서드 이용

decimal_number = 10
binary_representation = format(decimal_number, 'b')
print(binary_representation)  # 출력 결과: 1010

• 2진법 변환 방법3. format() 메서드 이용 - ‘{:b}’ 포맷 문자열 이용

decimal_number = 10

# '{:b}' 포맷팅 사용, 2진법으로
binary_representation = '{:b}'.format(decimal_number)
print(binary_representation)  # 출력 결과: 1010

• 2진법 변환 방법4. format() 메서드 이용 - ‘{:032b}’ 포맷 문자열 이용

n = 10
binary_representation = '{:032b}'.format(n) #32bit로 바꾸며 빈칸은 0으로 채우기
print(binary_representation)  # 출력 결과: 00000000000000000000000000001010

• 반대로 2진법을 10진법으로 바꿀 때는 문자열을 정수로 바꾸는 int()함수의 두 번째 인수에 2를 입력하면 됨

decimal_number = 101 #2진법 101
binary_representation = int(decimal_number, 2) #int(string, base)
print(binary_representation)  # 출력 결과: 5(십진법)

---

• string.zfill(길이)
  • 원래 문자열의 왼쪽에 ‘0’을 추가하여 문자열 길이를 지정된 길이로 맞추어줌.

original_string = "42"
padded_string = original_string.zfill(5)
print(padded_string)  # 출력 결과: 00042