파이썬 , 76 69 68 63 62 60 57 바이트

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

온라인으로 사용해보십시오!

작동 원리

이것은 입력을 받아 재귀 해결책 N 및 증분 유지 K 에서 시작 – 0 – 동안 모두 LSB _K (N) (비트 인덱스에서 K 오른쪽)와 MSB의 _K (N) (인덱스의 비트 K 왼쪽) 설정됩니다. 완료되면 모든 n 비트가 설정 되면 k를 반환 하고 그렇지 않으면 2k를 반환합니다.

보조 변수 t를 사용 하여 람다 f 를 명명 된 함수 F 로 다시 작성해 봅시다 .

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

각 호출에 F , 첫번째 비트 시프트 우리 N 개의 케이 우측 부와의 결과 저장 t를 . 이런 식으로 LSB ₀ (t) = LSB _k (n) 이므로 LSB _k (n) 이 설정된 경우에만 t 가 홀수 입니다.

MSB _k (n)의 설정 여부를 결정하는 것은 약간 까다 롭습니다. 이것이 n & t > t >> 1달성하는 것입니다. 그것이 어떻게 작동하는지 설명하기 위해 비트 길이 8 의 정수 n = 1αβγδεζη ₂ 를 고려 하고 함수 호출 F (n, 3) , 즉 k = 3을 분석해 봅시다 .

우리는 비교의 진실 값 (n & t> t >> 1) = (1αβγδεζη ₂ & 1αβγδ ₂ > 1αβγ ₂ ) 을 조사하여 MSB ₃ (n) = γ 가 설정되어 있는지 확인하려고합니다 . 관련된 정수를 살펴 보자.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

n & t> t >> 1 인 경우에만 γ = 1 이라고 주장합니다 .

• 만약 γ = 1 다음, n은 t가 비트 길이 갖는 5 동안 t >> 1 비트 길이를 갖는 4 이므로 n은 t> t >> 1 .

  이는 γ = 1이 n & t> t >> 1 임을 의미 합니다.

• 경우 n은 t> t >> 1 , 두 가지가있다 : 하나 γ = 1 또는 γ = 0 . 첫 번째 경우에는 증명할 것이 없습니다.

  두 번째 경우에는 αβγδ ₂ ≥ n & t> t >> 1 = 1αβγ ₂ 입니다.

  이후 αβγδ ₂ > 1αβγ ₂ 우리가 있어야 MSB ₀ (αβγδ ₂ ) MSB ≥ ₀ (1αβγ ₂ ) , 즉 저 α = 1 .

  이런 식으로 1βγδ ₂ > 11βγ ₂ 이므로 MSB ₁ (1βγδ ₂ ) ≥ MSB ₁ (11βγ ₂ )을 가져야 합니다. 즉, β = 1 입니다.

  차례로, 이는 11γδ ₂ > 111γ _2를 의미합니다 . 두 번째 경우에 γ = 0 임을 기억 하면 부등식 110δ ₂ > 1110 _2를 얻습니다 . 이는 MSB ₂ (110δ ₂ ) = 0 <1 = MSB ₂ (1110 ₂ ) 이므로 false 입니다.

  따라서 첫 번째 경우 만 가능하며 n & t> t >> 1은 γ = 1을 의미 합니다.

요약하면 LSB _k (n) 과 MSB _k (n) 이 모두 설정되면 t 는 홀수이고 n & t> t >> 1 은 True 가되므로 t & (n & t> t >> 1) 은 수율 1 . 그러나 LSB _k (n) 또는 MSB _k (n) 이 설정되지 않은 경우 (또는 둘 다인 경우), t 는 짝수이거나 n & t> t >> 1 은 False 이므로 t & (n & t> t> > 1) 은 0이 됩니다.

단일 인수로 F 를 호출 하면 k = 0이 초기화 됩니다. 앞에서 논의한 조건이 유지되는 동안, 이후의 코드 and가 실행되는데 ,이 코드 는 (다른 것들 중에서) 증가 된 k로 F 를 재귀 적으로 호출합니다 .

일단 LSB _K (N) 또는 MSB의 _K (N)가 해제되면, 조건이 실패하고 F가 (N, K)를 반환 0 . 앞의 k 함수 호출 각각은 (n & (n + 1)> 0) + 1 을 F (n, k) = 0 을 더하므로 F (n) 은 ((n & (n + 1)> 0) + 1) k .

이제 n의 모든 비트 가 같으면 (즉, n 이 0 이거나 모든 비트가 설정된 경우) n + 1 은 n 과 공통 인 비트를 가지지 않으므로 n & (n + 1) = 0 이고 F (n) 은 k를 반환합니다 . 그러나 n 에 설정 및 설정 해제 비트가 모두 있으면 n & (n + 1)> 0 이고 F (n) 은 2k를 반환합니다 .

답변

Btv`6L&)}x@q

B        % Input number (implicit). Horizontal vector of binary digits
tv       % Duplicate and concatenate vertically
`        % Do...while
  6L&)   %   Flatten the array if needed (in column-major order), and split it
         %   into two subarrays: one with the inner entries, and another
         %   with the two outer entries. The latter will be used for deciding
         %   if the loop continues or is exited
}        % Finally (execute before exiting the loop)
  x      %   Delete last subarray of inner entries
  @q     %   Push last iteration index minus 1
         % End (implicit). The next iterarion is executed if the array at the
         % top of the stack is non-empty and only contains nonzero values.
         % Otherwise the loop is exited, executing the "finally" block first
         % Display (implicit)

def f(n):b=bin(n)[2:];x=min(b.find('0'),b[::-1].find('0'));print(x<0)*len(b)or x*2

s=bin(input())[2:].split('0')
print len(min(s[-1],s[0]))<<1%len(s)

$a=[convert]::ToString($args[0],2)-split0;(((($b=$a[0].length),$a[-1].length|sort)[0]*2),$b)[$a.count-eq1]

f=
n=>n.toString(2).replace(/^(1*)(.*(\1))?$/,'$1$3').length

<input oninput=o.value=1/this.value?f(+this.value):''><input id=o readonly>