RSS Feed

임의 정수에 대한 비트 연산 OR의 작용

Problem 323

출제 일시 : 2021-01-22 00:00:25

y0, y1, y2,... 는 부호 없는(unsigned) 32비트 임의의 정수 수열입니다.
(즉, 0 ≤ yi < 232이고 모든 값의 등장 확률은 동일합니다).

xi는 다음과 같이 재귀적으로 정의되는 수열입니다:

  • x0 = 0
  • i > 0일 때, xi = xi-1| yi-1. ( |는 비트 연산 OR입니다)

이렇게 정의하면 결국에는 특정한 색인 N에서 xi = 232 -1 (모든 비트가 1)이 되고, 모든 색인 i ≥ N에서 그렇다는 것을 증명할 수 있습니다.

N의 기댓값을 구하세요.
답은 소수점이하 10자리까지 반올림해서 제출하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.