2진수 최 좌측 1자리 찾기

2021.05.02 - [Problem Solving] - 2진수 최 우측 1의 자리 찾아내기

우측 찾기에 이어서 최 좌측 1자리를 찾을 일이 있어서 Blog를 남겨 본다.

가장 쉬운 방법은

while(1 < target) {
    count++;
    target=>>1;
}

일 것이다. 이것은 O(N)이 필요 함으로 속도를 높이는 방법을 찾아 보자.

ori |= (ori >> 1);
ori |= (ori >> 2);
ori |= (ori >> 4);
ori |= (ori >> 8);
ori |= (ori >> 16);

return ori - (ori>>1)

위는 O(Log N)의 속도로 가장 좌측 1을 찾게 되는 방법이다.

기본적인 아이디어는 copy and paste다.

10000001 

이 있을 경우 1bit를 우측으로 옮기고 or해서 붙이면

11000001

좌측 2비트는 무조건 11이 되게 된다 이것을 다시 2bit 우측으로 더 옮기면

11110001

이 되고 다시 4bit를 옮기면

11111111 이 되게 된다.

이것을 signed 기준 32bit까지 옮기고 1비트를 우측으로 옮기면

1111111 이 되게 되고 기존 bit와 빼기를 하면

11111111 - 1111111로 최 좌측 1비트만 남고 나머지는 모두 사라지게 된다.

10000000