작은 숫자 가 큰 숫자에서 비트를 빌릴 수 있다는 것을 알고 있습니까? 다음은 예입니다. 두 개의 숫자 5와 14를 가정 해 봅시다. 먼저 이진수로 쓰십시오.
5 14
000101 001110
먼저 우리는 가장 작은을 에 떨어져 많은 수의 비트, 우리는 가장 작은에게주고 떨어져 다른 수에 비트. 그래서
This bit turns off
|
v
000101 001110
^
|
This bit turns on
이제 우리는
000111 001100
우리의 숫자는 7과 12입니다. 첫 번째 숫자는 여전히 작기 때문에 계속 진행합니다.
000111 001100
001111 001000
이제 우리는 15와 8을 가지고 있으므로 멈출 수 있습니다. 이 작업 집합을 “비트 차용”두 숫자라고합니다. 다른 예를 봅시다. 20과 61.
20 61
010100 111101
010101 111100
010111 111000
111111 100000
63 32
최종 결과는 32, 63 입니다. 한 번 더 해봅시다 . 31, 12. 31은 이미 12보다 큽니다. 따라서 할 일이 없습니다! 비트 차입 31 및 12는 31 및 12를 변경하지 않습니다.
도전
당신의 도전은 두 개의 숫자를 취하여 비트 차용하는 프로그램이나 함수를 작성하는 것입니다. 두 숫자는 항상 양의 정수입니다. 입력 및 출력 형식은 합리적입니다.
IO 테스트 :
Input: 2, 3
Output: 3, 2
Input: 3, 2
Output: 3, 2
Input: 8, 23
Output: 31, 0
Input: 42, 81
Output: 63, 0
Input: 38, 41
Output: 47, 32
Input: 16, 73
Output: 23, 0
Input: 17, 17
Output: 17, 17
표준 허점이 적용되고 바이트 단위의 최단 답변이 승리합니다!
답변
젤리 , 11 바이트
~1¦&N$^µ</¿
온라인으로 사용해보십시오! 또는 모든 테스트 사례를 확인하십시오 .
배경
정수 n 의 마지막 세트 비트 를 다음과 같이 추출 할 수 있습니다 .
n + 1 은 n의 모든 후행 설정 비트 와 인접 비 설정 비트를 토글합니다 . 예를 들어, 10011 2 + 1 = 10100 2 입니다.
이후 ~ N = – (N + 1) = -N – 1 , -n = ~ N + 1 , 그래서 -n NOT의 비트에 상기 적용되는 N (토글 모든 따라서 마지막 전에 모든 비트를 토글 링, 비트) 1 .
예를 들어, -10100 2 = ~ 10100 2 + 1 = 01011 2 + 1 = 01100 2 입니다.
취하여 -n n은 비트 단위 AND의 N 및 -n (부등에 보낸 마지막 비트 전에 설정된 모든 비트는 무효화되어 N 및 -n 따라서 마지막 비트 세트 수득) N을 .
예를 들어, 10100 2 & -10100 2 = 10100 2 & 01100 2 = 00100 2 입니다.
따라서, 배타적 논리합 N을 가진 N -n 및 설정 해제의 마지막 비트 세트 N을 .
반대로, n 의 마지막 세트 비트를 설정 해제하려면 위 의 수식 을 ~ n 에 적용 하면 수식 n ^ (~ n &-~ n)이 파생 됩니다.
작동 원리
~1¦&N$^µ</¿ Main link. Argument: A (list of pairs)
¿ While loop:
</ Condition: Reduce p by less-than. True iff x < y.
µ Body chain:
~1¦ Apply bitwise NOT to the x, first item of the pair.
$ Convert the two links to the left into a monadic chain.
N Negate; multiply [~x, y] by -1, yielding [-~x, -y].
& Logical AND. Yields [-~x & ~x, -y & y].
^ Vectorized XOR with p. Yields [(-~x & ~x) ^ x, (-y & y) ^ y].
답변
J, 31 26 바이트
,`(($:~(OR>:))~(AND<:))@.<
재귀와 비트 트릭을 사용하는 간단한 접근 방식. 값 n에 대해 가장 오른쪽에있는 1 비트를 끄고 ( 0으로 설정 ) n 과 n -1 사이에서 비트 단위로 수행하고 가장 오른쪽 에 1을 설정하여 설정할 수 있습니다 값 n에 대해 off ( 0 ) 비트의 경우 비트 단위 또는 n 과 n +1 사이에서 수행 할 수 있습니다 .
용법
입력은 두 개의 정수로 구성되며, 하나는 LHS에 적용되고 다른 하나는 RHS에 적용되며, 출력은 비트 차용 된 값의 목록입니다.
f =: ,`(($:~(OR>:))~(AND<:))@.<
2 f 3
3 2
3 f 2
3 2
8 f 23
31 0
42 f 81
63 0
38 f 41
47 32
16 f 73
23 0
17 f 17
17 17
설명
,`(($:~(OR>:))~(AND<:))@.< Input: x on LHS, y on RHS
If x < y,
, Form a 2-element array [x, y] and return
Else
<: Decrement y
AND Perform bitwise-and on y and y-1, call it y'
>: Increment x
OR Perform bitwise-or on x and x+1, call it x'
$: Call recursively on x' and y' and return
답변
파이썬, 42 바이트
f=lambda x,y:x<y and f(x|x+1,y&y-1)or(x,y)4 바이트로 골프를 치는 @ jimmy23013에게 감사드립니다! 2 바이트를 골라 낸 @LeakyNun에게 감사드립니다!
Ideone에서 테스트하십시오 .
답변
매스 매 티카, 46 바이트
If[#<#2,BitOr[#,#+1]~#0~BitAnd[#2,#2-1],{##}]&
J의 솔루션 에서 사용한 것과 동일한 방법 입니다.
1 바이트를 절약하고 infix 응용 프로그램을 상기시켜주는 @ Martin 에게 감사드립니다 ~.
용법
입력은 두 개의 정수 인수로 구성되며 출력은 비트 차용 된 값이있는 목록입니다.
답변
Pyth, 29 27 25 22 21 20 19 18 16 바이트
MxG ^ 2x _ + \ 0.BG`HCm.W <FHgVZU2dCMxG ^ 2x_ + 0jG2HCm.W <FHgVZU2dCCm.W <FH.bxN ^ 2x_ + 0jN2YZ2dCm.W <FH.bxN ^ 2x_출력 변경 형식mW <FH.exb ^ 2x_ + 0jb2kZm.W <FH.U ,. | bhb. & ZtZZ.W <FH.U ,. | bhb. & ZtZZ<-변경된 입력 / 출력 형식.W <FH.U ,. | bhb. & ZtZ.W <FH.U ,. | bhb. & t
답변
답변
미로 , 37 34 바이트
?"
}
|=:{:
) }
: :;-{
=&( {!;\!@
설명
빠른 미로 입문서 :
- 미로는 임의 정밀도 정수 두 스택상에서 동작 메인 및 보조 초기에 제로의 (내재) 무한대로 채워진다.
- 소스 코드는 명령 포인터 (IP)가 복도를 따르는 미로와 유사합니다. 모든 흥미로운 제어 흐름은 정션에서 발생합니다. IP에 둘 이상의 셀이있는 경우 기본 스택의 맨 위가 검사됩니다. 값이 음수이면 IP가 왼쪽으로 돌아가고 양수이면 IP가 오른쪽으로 돌아가고 그렇지 않으면 직진합니다. 선택한 방향이 벽 (예 : 공간)으로 막히면 IP가 반대 방향으로 이동합니다.
이 프로그램은 다른 답변과 같은 알고리즘을 사용 : 우리는 대신 (a, b)에 (a | a+1, b & b-1)긴만큼 a < b. 골프를 좀 더 시도한 후에 전체 설명을 추가하겠습니다.
IP는 왼쪽 상단에서 시작하여 오른쪽으로 이동합니다. ?정수를 읽습니다 a. 그런 다음 "no-op이지만 IP가 즉시 아래로 이동하는 것을 방지해야합니다. 이것은 또한 막 다른 골목이므로 IP는 돌아 서서 ?다시 읽습니다 b. }다음 이동 b에서 주요 하기 AUX 그래서 지금 우리가 가지고 :
Main [ ... 0 a | b 0 ...] Aux
그런 |다음 a및 의 비트 단위 OR을 사용하므로 아무 것도 수행하지 않습니다 0. 우리 a는 항상 긍정적이라는 것을 알고 있기 때문에 IP는 동쪽으로 바뀝니다. 프로그램의 메인 루프가 시작됩니다. 우리는 비교하기 위해 짧은 직선 섹션 시작 a과 b:
= Swap tops of stacks, i.e. swap a and b.
: Duplicate b.
{ Pull a over to main.
: Duplicate a.
} Push one copy back to aux.
- Compute b-a.
IP는 이제 다른 교차점에 있습니다. 먼저 결과가 긍정적 인 경우를 생각해 봅시다. 즉 b > a, 반복을 한 번 더 수행해야합니다. 반복도 완전히 선형입니다. 스택은 현재 다음과 같습니다.
Main [ ... 0 b (b-a) | a 0 ...] Aux
; Discard b-a.
: Duplicate b.
( Decrement.
& Bitwise AND with b, clearing the least-significant 1.
= Swap new b with old a.
: Duplicate a.
) Increment.
| Bitwise OR with a, setting the least-significant 0.
그리고 우리는 루프의 시작으로 돌아갑니다 ( a다시 긍정적이기 때문에 IP는 다시 동쪽으로 바뀝니다).
어떤 시점 b-a에서 더 이상 긍정적이지 않으면 IP는 다른 두 경로 중 하나를 사용합니다. 두 경우 모두에서 우리가 가져 오는 것을 참고 a로 {다음의 IP는 굽힘을 다음 코너에 충돌 한 후 인쇄 a와 함께 !. 이제 스택의 상단이 다시 b-a나타납니다. 두 경우 모두 IP가 동쪽으로 이동합니다. 이제 남은 것은 짧은 선형 비트입니다.
; Discard b-a.
\ Print a linefeed.
! Print b.
@ Terminate the program.