1Day 1Algorithm

[DAY 5] Flipping bits

walk_through_me 2019. 10. 5. 23:48
 

Flipping bits | HackerRank

Flip bits in its binary representation.

www.hackerrank.com

You will be given a list of 32 bit unsigned integers. Flip all the bits ( and ) and print the result as an unsigned integer.

For example, your decimal input n = 9(10) = 1001(2). We're working with 32 bits, so:

00000000000000000000000000001001(2) = 9(10)

11111111111111111111111111110110(2) = 4294967286(10)

 

 

풀이

function flippingBits(N) {
    const refVal = Math.pow(2, 32) - 1;
    return refVal - N;
}

문제는 결국 2의 32제곱에서 1을 뺀 값에서 주어진 N을 빼주는 것과 같음(XOR*).

 

XOR(배타적 논리합) 

두 개의 명제 가운데 1개만 참일 경우를 판단하는 논리연산

A B 결과
1 1 0
1 0 1
0 1 1
0 0 0

 

 

다른 사람의 풀이

function flippingBits(N) {
    return ~ N >>> 0;
}

부호 버림 오른쪽 시프트(>>>)*와 Not(~) 비트 연산자를 이용했네.

먼저 N을 ~ 연산자로 반전시키고, >>> 연산자로 부호를 없애 버림👍🏻

ex. (N) 2147483647 → (~ N) -2147483648 →  (~N >>> 0) 2147483648

 

 

부호 버림 오른쪽 시프트(Zero-fill right shift)
a >>> b

오른쪽으로 b만큼 이동하고, 오른쪽으로 시프트 된 비트는 버려지고, 왼쪽에서 0비트가 옮겨짐(이 때문에 부호비트는 항상 0이되므로, 음수가 아니게 됨!)

양수 일 때, a >> b 와 같은 결과, 음수 일 경우 같지 않음