첫 번째 비트와 마지막 비트만 설정된 숫자 출력하기

이 문제의 목표는 주어진 숫자 n 이하의 범위에서, 첫 번째 비트(최상위 비트)와 마지막 비트(최하위 비트)만 1로 설정되어 있고 나머지 비트는 모두 0인 숫자들을 모두 찾아 출력하는 것입니다.

컴퓨터 언어에서 설정된 비트(set bit)란 값이 1인 비트를 의미하며, 설정되지 않은 비트(unset bit)는 값이 0인 비트를 뜻합니다.

입력: num의 값 = 5
출력: 1 3 5
   1은 이진수로 1에 해당합니다
   3은 이진수로 11에 해당합니다
   5는 이진수로 101에 해당합니다

알고리즘

시작
1단계 -> unsigned int형 변수 num=5와 int형 변수 i=1을 선언한다
2단계 -> i 값을 출력한다
3단계 -> i=3부터 i<=num까지 반복 (++i)
   IF (!(i-1 & i-2))
     i를 출력한다
   End
End
종료

동작 원리

핵심 조건은 !(i-1 & i-2)입니다. 어떤 수 i가 2^k + 1 형태라면, i-1은 2^k(이진수 1000...0)가 되고, i-2는 2^k - 1(이진수 0111...1)이 됩니다. 이 두 수를 비트 AND 연산하면 서로 겹치는 1비트가 없으므로 결과는 항상 0이 됩니다. 즉, 이 조건을 통과하는 수는 정확히 첫 번째 비트와 마지막 비트만 1로 설정된 수입니다.

예제

#include <stdio.h>
int main(int argc, char const *argv[]) {
   unsigned int num = 5;
   int i = 1;
   printf("%d ", i); // 첫 번째 숫자 1 출력
   for (i = 3; i <= num; ++i) {
      if(!(i-1 & i-2)) // i-1과 i-2에 대해 AND 연산 수행
      printf("%d ", i);
   }
   return 0;
}

출력

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

1 3 5