C++로 숫자에 연속된 세트 비트(1)가 있는지 확인하는 방법

이 글에서는 어떤 수의 이진수 표현에 인접한 세트 비트(set bit, 즉 1)가 존재하는지 확인하는 방법을 알아봅니다. 예를 들어 숫자 12는 이진수로 1100이므로 연속된 두 개의 1을 가지고 있습니다.

이를 확인하는 아이디어는 매우 간단합니다. 숫자를 오른쪽으로 1비트 시프트한 뒤, 원래 값과 비트 AND 연산을 수행합니다. 그 결과가 0이 아니라면 어딘가에 연속된 1이 반드시 존재한다는 의미입니다. 시프트를 하면 원래 인접해 있던 1들이 같은 자리에 겹치게 되므로, AND 연산 결과에 1이 남게 되는 원리입니다.

예제 코드

#include <iostream>
using namespace std;

bool hasConsecutiveOnes(int n) {
    // 시프트 후 AND 결과가 0이 아니면 연속된 1이 존재
    return (n & (n >> 1)) != 0;
}

int main() {
    int num = 67; // 이진수: 1000011
    if (hasConsecutiveOnes(num)) {
        cout << "연속된 1이 있습니다";
    } else {
        cout << "연속된 1이 없습니다";
    }
    return 0;
}

출력

연속된 1이 있습니다

동작 원리

숫자 67은 이진수로 1000011입니다. 이 값을 오른쪽으로 1비트 시프트하면 0100001이 되고, 두 값의 AND 연산 결과는 0000001이 됩니다. 결과가 0이 아니므로 연속된 1이 존재한다고 판단할 수 있습니다.

주의할 점

AND 연산 결과를 1과 직접 비교하는 것은 위험합니다. 예를 들어 숫자 7(이진수 111)의 경우, 시프트한 값 11과의 AND 결과는 11(십진수 3)이 되어 1이 아니기 때문입니다. 따라서 결과가 0인지 아닌지(!= 0)를 확인하는 것이 정확하고 안전한 방법입니다.