태그 보관물: bitwise

bitwise

“비트 빌린”두 숫자 15와 8을 가지고 있으므로

작은 숫자 가 큰 숫자에서 비트를 빌릴 수 있다는 것을 알고 있습니까? 다음은 예입니다. 두 개의 숫자 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 + 1n의 모든 후행 설정 비트 와 인접 비 설정 비트를 토글합니다 . 예를 들어, 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으로 설정 ) nn -1 사이에서 비트 단위로 수행하고 가장 오른쪽 에 1을 설정하여 설정할 수 있습니다 값 n에 대해 off ( 0 ) 비트의 경우 비트 단위 또는 nn +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 <FHgVZU2dC 
MxG ^ 2x_ + 0jG2HCm.W <FHgVZU2dC 
Cm.W <FH.bxN ^ 2x_ + 0jN2YZ2dC 
m.W <FH.bxN ^ 2x_       출력 변경 형식
 mW <FH.exb ^ 2x_ + 0jb2kZ 
m.W <FH.U ,. | bhb. & ZtZZ 
.W <FH.U ,. | bhb. & ZtZZ          <-변경된 입력 / 출력 형식
 .W <FH.U ,. | bhb. & ZtZ
.W <FH.U ,. | bhb. & t

테스트 스위트.


답변

05AB1E, 16 15 바이트

[D`›#`D<&sD>~s‚

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


답변

미로 , 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는 동쪽으로 바뀝니다. 프로그램의 메인 루프가 시작됩니다. 우리는 비교하기 위해 짧은 직선 섹션 시작 ab:

=   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.