두 비트 블록 더브 테일
두 비트 블록이 완벽하게 도브테일되는지 확인합니다.
명세서
비트 블록은 예를 들어 11110101 과 같이 8 비트의 고정 된 시퀀스입니다 .
단순화를 위해
truthy/falsey값을1/0비트로 지칭 하지만 두 상태를 명확하고 잘 정의 된 일관된 방식으로 표현할 수있는 모든 것이 될 수 있습니다. 예를 들면 다음과 같습니다.0/1x/yFalse/True"false"/"true"'a'/'b'[]/[...]odd/even>0 / <00 / !0
완벽하게 더브 테일이란 무엇을 의미합니까?
한 블록의 1 비트는 다른 블록의 0 또는 외부 블록에만 들어갈 수 있습니다.
전체 블록을 왼쪽이나 오른쪽으로 이동할 수 있지만 블록을 수정하거나 되돌릴 수는 없습니다.
결과 블록에는 입력 된 두 블록의 모두 1과 그 블록 만 포함되어야합니다.
후행 및 선행 0이있을 수있는 동안 1 사이에 0이 없어야합니다.
결과 블록은 8 비트보다 길 수 있습니다.
예
입력 : [10010111, 01011010]
10010111
↓ ↓ ↓↓↓
01011010 <-shif x 2
결과 0111111111 => 완벽하게 더브 테일
입력 : 두 개의 비트 블록.
- 빈 블록 (모두 0)을 처리 할 필요가 없습니다.
출력 : 솔루션은 입력 블록이 위에서 설명한대로 완벽하게 일치하는지 여부를 명확하게 명시해야합니다.
- 결과 블록은 유효한 대답이 아닙니다.
테스트 케이스.
00000000, 00000000 | you don't
00000000, ... | need to
... , 00000000 | handle these
11111111, 11111111 -> True
11111111, 10000000 -> True
11110000, 00101000 -> False
00101000, 10100000 -> True
10000000, 00111000 -> True
00110011, 11001100 -> True
00010000, 11101010 -> False
10000100, 10111101 -> True
01111010, 01011111 -> True
10010101, 00001101 -> False
01010011, 10110000 -> True
00000111, 00010011 -> False
00000011, 00000101 -> False
규칙
- 임의의 편리한 방법으로 입출력을 할 수 있습니다 .
- STDOUT에 인쇄하고 함수 결과 또는 오류 메시지로 반환 할 수 있습니다.
- 전체 프로그램 또는 기능이 허용됩니다.
- 표준 허점 은 금지됩니다.
- 이것은 코드 골프 이므로 모든 일반적인 골프 규칙이 적용되고 가장 짧은 코드 (바이트 단위)가 이깁니다.
모래 상자
답변
JavaScript (ES6), 63 54 52 50 바이트
내 C 답변에서 @AZTECCO가 제안한 것과 유사한 최적화를 적용하여 2 바이트를 절약했습니다.
를 예상합니다 (a)(b). 여기서 a 와 b 는 바이트입니다. 블록이 완벽하게 더브 테일 할 수 있으면 0을 반환 하고 그렇지 않으면 1을 반환합니다.
a=>g=b=>b?a<<8&b|(c=a<<8|b,c+=c&-c)&c-1&&g(b<<1):1
온라인으로 시도하십시오!
어떻게?
재귀 함수 g 는 다음 조건이 모두 충족 될 때까지 b 를 한 번에 한 위치 씩 왼쪽 으로 이동하려고합니다 .
(a << 8) & b0 과 같습니다 . 즉 a << 8 이고 b 는 공통된 세트 비트를 갖지 않습니다.c = (a << 8) | b연속 시퀀스이고 1 의가 가능 후단 뒤에 0 들 '
두 번째 테스트에서는 c 에 가장 오른쪽에 설정된 비트를 c에 추가 하고 연속 된 1 의 시퀀스를 따라 전파를 전달 하여 단일 1 결과인지 확인합니다 .
다음 비트 트릭을 사용합니다.
c & -c // returns the rightmost set bit in c
c & (c - 1) // returns c without the rightmost set bit in c
// (0 if c is an exact power of 2)
예:
0111111000 + (0111111000 & -0111111000) = 0111111000 + 0000001000 = 1000000000
1000000000 & (1000000000 - 1) = 1000000000 & 0111111111 = 0
b = 0모든 비트가 버려 졌음을 의미하는 경우 재귀를 중지합니다 . (이것이 우리가 b << 1대신하는 이유 입니다 b * 2. 그래서 b 는 IEEE 754 부동 소수점 숫자가 아닌 32 비트 정수로 강제됩니다.)
Python 3 , 68 바이트
lambda a,b:any(a<<8&b<<x==('01'in bin(a<<8^b<<x))for x in range(17))
온라인으로 시도하십시오!
이 함수는 두 이진 시퀀스의 모든 중첩 구성을 시도합니다. xor각 구성에 대해 비트 단위 를 수행하고 모든 결과 1가 연속적 인지 확인합니다 . 이것은 xor연산 결과가 선행 되는 일부 경우에 대해 거짓 양성을 제공 0하므로 추가적으로 비트 and연산이 양보 하는지 확인합니다 0.
xnor 덕분에 -4 바이트
Python 2 , 78 59 57 바이트
출력은 종료 코드를 통해 이루어집니다. 프로그램은 진실 입력에 대해 실패 (1)하고 거짓 입력에 대해 완료 (0)합니다. 입력은 두 개의 음이 아닌 정수입니다.
이것은 이제 Arnauld 의 답변 과 매우 유사 하지만 이 웹 사이트 에서 d&-d트릭을 발견했습니다 .
a,b=input()
b<<=8
exec"d=a|b;a&b<1>d&(d&-d)+d>q;a*=2;"*17
온라인으로 시도하십시오!
C (gcc) , 61 58 57 53 바이트
@AZTECCO 덕분에 4 바이트 절약
내 JS 답변 의 포트 .
블록이 완벽하게 더브 테일 할 수 있으면 0을 반환 하고 그렇지 않으면 0이 아닌 정수를 반환합니다.
c;f(a,b){for(a<<=8;b&&a&b|(c=a|b,c+=c&-c)&c-1;b*=2);}
온라인으로 시도하십시오!
젤리 , 18 17 바이트
T_8+Ɱ17;ṢIPʋ€T}1e
8 개의 1/0으로 구성된 두 개의 목록을 수락하는 이원 적 링크 1는 더브 테일하거나 0그렇지 않은 경우 양보 합니다 .
온라인으로 시도하십시오! 또는 테스트 스위트를 참조하십시오(8 개의 진실 케이스와 5 개의 거짓 케이스를 갖도록 재정렬했습니다).
아마도 간결한 방법이있을 것입니다 ...
어떻게?
T_8+Ɱ17;ṢIPʋ€T}1e - Link: block A; block B
T - truthy indices of A
_8 - subtract eight from each
17 - seventeen
+Ɱ - map with addition -> a list of the 17 shifted versions of T
€ - for each:
T} - using the truthy indices of B as the right argument
ʋ - last four links as a dyad:
; - concatenate
Ṣ - sort
I - incremental differences
P - product (0 if two 1-bits collide; >1 if zero-gaps would result)
1e - does 1 exist in that result?
05AB1E , 18 바이트
¬0*æδì`âε0ζO0ÚPΘ}à
한 쌍의 비트 정수 목록으로 입력하면 각각 진실 / 거짓에 대해 1/ 0를 출력 합니다.
온라인으로 시도 하거나 모든 테스트 사례를 확인하십시오 . (테스트 스위트에는 Ù뒤에 추가가 포함되어 있습니다. æ그렇지 않으면 시간이 초과됩니다. 단일 TIO는이 균일화없이 약 35-40 초가 걸립니다.)
설명:
¬ # Push the first list of the (implicit) input-pair (without popping)
0* # Multiply each value by 0 to create a list of 0s of that same length
æ # Get the powerset of this list of 0s (including empty list)
# (prefixes builtin would be preferably here, but unfortunately it lacks
# an empty list; obviously this powerset contains a lot of duplicated
# lists, which is why the uniquify `Ù` in the test suite is used to
# make the program faster)
δ # Apply double-vectorized (using the powerset of 0s and implicit input)
ì # Prepend the list of 0s to the inner input-list
` # Pop and push both list of lists separated to the stack
â # Use the cartesian product to get every possible pair of inner lists
ε # Map each pair of lists to:
ζ # Zip/transpose; swapping rows/columns,
0 # using a 0 as trailing filler-item if the lists are unequal in length
O # Sum each inner pair
0Ú # Remove all leading and trailing 0s from this list
P # Take the product of the remaining values
Θ # And check that this is equal to 1
}à # After the map: check if any are truthy by taking the maximum
# (after which this is output implicitly as result)
입력에서 출력까지 단계별로 온라인에서 시도해보십시오 (속도를 높이기 위해 uniquify 사용).
Husk , 15 바이트
VΠ¤×ż≠ö→kΣQṠ+mṗ
온라인으로 시도하십시오! 또는 테스트 케이스를 확인하십시오. 출력은 진실 인 경우 양의 정수이고 거짓 인 경우 0입니다.
설명
명확성을 위해 괄호가 추가되었습니다.
VΠ¤(׿≠)(→kΣQ(Ṡ+mṗ)) Implicit inputs: two lists of integers.
¤( A )( B ) Apply B to both and combine with A.
→kΣQ(Ṡ+mṗ) Argument is a list x.
m Map
ṗ primality test
Ṡ+ and concatenate before x.
Since 0 and 1 aren't primes, this effectively prepends 8 zeros.
Q All contiguous slices.
k Classify (into separate lists)
Σ by sum.
→ Get the last class, i.e. the slices with maximal sum.
They are those that contain all the 1s of x.
׿≠ Combining function:
× Cartesian product by
ż zip (preserving overflowing elements) by
≠ absolute difference.
Now we have a list of all combinations of slices from both extended lists,
with 1 and 1 producing 0.
V Does any of them have
Π nonzero product (all 1s)?
C (gcc) , 105 \$\cdots\$ 63 62 바이트
그 자신 Arnauld 덕분에 무려 13 바이트를 절약했습니다 !!! AZTECCO
덕분에 바이트를 절약했습니다 !!!
t;f(a,b){for(a<<=t=8;b&&t;b*=2)t=a|b,t/=t&-t,t=a&b|t&-~t;t=b;}
온라인으로 시도하십시오!
반환 \$!0\$true 및 \$0\$ 그렇지 않으면.
설명
첫 번째 매개 변수 \를 이동합니다.$a\$, \ 이상$8\$두 번째 매개 변수 \를 이동하여 모든 다른 이동 위치를 시도 할 수 있습니다.$b\$. \의 모든 시프트에 대한 루프$b\$모든 비트가 \ 와 다른지 확인$a\$및 \$b\$하나 개의 연속 블록을 형성 \$1\$s와 결합 될 때 \$a\$.
Retina 0.8.2 , 82 81 바이트
$'¶$`;
(.+),(.*;.*)
$2,$1
+`;(.)(.*),(.)
-$1$3;$2, -(0|(1))+ $#2
;|,
m`^0*1+0*$
온라인으로 시도하십시오! 링크에는 테스트 케이스가 포함됩니다. 설명:
$'¶$`;
;모든 위치에 s를 삽입 하여 입력의 복제본을 만듭니다 .
(.+),(.*;.*)
$2,$1
두 입력이 두 ;번째 안에 있으면 두 입력을 바꿉니다 .
+`;(.)(.*),(.)
-$1$3;$2,
사이의 부분 긴밀히하려고 ;하고을 ,다른 입력으로.
-(0|(1))+
$#2
각 중첩의 비트 수를 계산합니다.
;|,
구분 기호를 삭제하십시오.
m`^0*1+0*$
더브 테일이 유효한 결과를 생성했는지 확인합니다. 편집 : 유효한 결과에 대해 0이 아닌 값을 반환하여 1 바이트를 저장했습니다 (입력을 연결하는 것이 유효한 더브 테일링 인 경우 값은 가능한 더브 테일링 수에 1을 더한 값입니다).
Perl 5 -p , 68 바이트
s/\b0+|0+\b//g;s/(1*)(.*?)(1*) //;y/01/10/;$_=/^(0*$1)?$2(${3}0*)?$/
온라인으로 시도하십시오!
s/\b0+|0+\b//g두 블록에서 0을 자릅니다.s/(1*)(.*?)(1*) //첫 번째 인수를 제거하고 3 개의 그룹을 캡처하는 대체 :- $ 1 : 왼쪽 것
- $ 2 : 가장 짧은 시퀀스
- $ 3 : 올바른 것 (결국)
y/01/10/남은 두 번째 인수의 음역 (비트 아님)/^(0*$1)?$2(${3}0*)?$/패턴 두 번째 인수 (반전)가 일치해야합니다.
계수 , 149139 바이트
: d ( a b -- ? ) [ 8 [ 0 suffix ] times 15 rotate ] bi@
all-rotations [ dupd [ + ] 2map [ 0 = ] trim all-equal? ] map
f [ or ] reduce nip ;
온라인으로 시도하십시오!
입력을 정수 배열로 가져옵니다.
순진한 솔루션-두 배열을 8 개의 추가 0으로 채운 다음 두 번째 배열의 각 회전을 첫 번째 배열에 추가하고 선행 / 후행 0을 트리밍하고 결과 배열이 하나의 숫자로만 구성되는지 확인합니다 (1).
x86 32 비트 기계어 코드, 27 바이트
x86-64 버전은 int dovetail(dummy, unsigned x, unsigned y);더브 테일의 경우 EAX = 0을 반환하고 그렇지 않은 경우 0이 아닌 C에서 호출 할 수 있습니다 . 더브 테일하지 않는 0이 아닌 입력에 대한 모든 실행 경로는 EAX=(x<<n)|y반환하기 전에 EAX에서 계산 된 마지막 항목으로 이어집니다. 또한 더 간단하고 분명하게 도브테일의 경우 ZF = 1, 그렇지 않은 경우 ZF = 0을 반환합니다.
온라인으로 시도하십시오! . NASM 목록 : 오프셋, 기계 코드, 소스
1 dovetail: ; bool dovetail (ESI, EDX)
2 00000000 86F2 xchg dh, dl ; shl edx,8 ; upper bytes are zero
3 .loop:
4 00000002 85F2 test edx, esi
5 00000004 7510 jnz .overlap ; skip any bit conflicts
6
7 00000006 8D0432 lea eax, [edx+esi] ; equivalent to | or ^ for non-overlapping bits
8 00000009 0FBCC8 bsf ecx, eax ; count trailing zeros
9 0000000C D3E8 shr eax, cl ; shift out low zeros
10 0000000E 40 inc eax ; turn contiguous low bits into 1 set bit
11
12 0000000F 8D48FF lea ecx, [eax-1] ; clear lowest set bit
13 00000012 21C8 and eax, ecx ; like blsr eax, eax
14 00000014 7404 jz .dovetail_found ; there was only 1 set bit, now 0
15 .overlap:
16 00000016 01F6 add esi, esi
17 00000018 79E8 jns .loop ; keep looping until ESI hits the top
18
19 .dovetail_found:
20 ;; return value in ZF:
21 ; 1 for dovetail detection by BLSR
22 ; 0 for exiting loop via ESI setting SF: implies non-zero
23 0000001A C3 ret
보다 https://catonmat.net/low-level-bit-hacks 가장 낮은 세트 비트를 분리하거나 지우는 것을 포함한 비트 핵 트릭에 대한 개요를 참조하십시오.
대체 버전 :
BMI1 blsr eax, eax은 lea edx, [rax-1]/ 와 같은 5 바이트 and eax, edx입니다. BMI1 (Haswell +, Piledriver +)이 필요합니다. 내가 사용하는 and대신 testEAX의 정수 결과를 사용할 것 때문에.
BMI1 blsi ecx, eax(5B) / add eax, ecx(2B) ( eax += lowest_set_bit(eax))는 연속적인 비트 범위를 단일 세트 비트로 바꾸는 가장 짧은 방법이 아닙니다 . 대신, 32 비트 코드에서 bsf/ shr/ inc저장 한 1 바이트로 맨 아래로 이동 하면 총 6 바이트가 연속 비트 범위를 단일 세트 비트로 변환합니다. x86-64 버전 (단일 바이트 inc인코딩 없음)은 BMI1을 사용할 수있는 경우이를 수행하여 동일한 코드 크기로 명령을 저장할 수 있습니다.
나는 x & y == 0비트를 결합하는 것과는 별도로 테스트 를하지 않기를 바랐다 . 예를 들어 이들을 함께 XOR 하고 입력 중 하나의 하단에서 연속적인 비트 범위가 시작되었는지 확인합니다.
mov eax, edx
xor eax, esi
jz .all_cancelled ; exclude all-zeros from the 1-set-bit test
blsi ecx, esi ; isolate lowest set of the shifting input
add eax, ecx ; carry turns contiguous set bits into 1
; BROKEN, need blsi(esi|edx)
그러나 우리는 XOR 결과의 가장 낮은 세트 비트를 사용할 수 없습니다. 일부 충돌하는 비트는 서로를 취소했을 수 있습니다. 예를 들어 x = 0b110010 y = 1은 x ^ (y<<1) = 0b110000모든 세트 비트가 연속적 일 때 거짓 양성을 제공합니다 .
그리고 그것은 당신이 이동하는 입력의 가장 낮은 세트 비트를 분리하는 데는 작동하지 않습니다. 당신이 다른 입력의 가장 낮은 설정 비트를지나 왼쪽으로 이동하면, 당신은 추가 할 필요가 그 대신에 고립 된 비트. 예를 들어 다음과 같은 입력을 사용하여 내 첫 번째 버전으로 잘못-처리했다 xor그리고 blsi ecx, esi그것은 단지 ESI의 최하위 비트는 EDX의 가장 낮은 설정 비트를지나 왼쪽으로 이동할과 일 맥상 때문이다.
mov edx, 0b0110010
mov esi, 0b1001100
이 방법은 어떤 종류의 min(blsi(x), blsi(y)), 또는 에서도 여전히 작동 할 수 blsi(x|y)있지만 별도로 수행하는 것은 승리가 아닙니다.
C (gcc) , 94 82 71 70 바이트
편집 : Noodle9의 유사한 C 답변을 살펴보고 여기에서 사용할 수있는 모든 골프 트릭을 뻔뻔스럽게 훔쳐서 -12 바이트 ... 그것도 upvote하십시오!
더 많은 편집 : ... Arnauld에서 훔친 다양한 팁과 트릭 덕분에 -12 바이트 더 ...
c;i;f(a,b){for(b<<=9,i=18;i-->1;i*=a&b||c&c++)a*=2,c/=(c=b|a)&-c;i=i;}
온라인으로 시도하십시오!
'C'의 첫 번째 대답 (처음에는 부끄럽게 작동하지 않았습니다. 버그를 발견 한 Arnauld에게 감사드립니다 ...).
입력은 두 개의 8 비트 정수이며, 입력 비트가 완벽하게 서로 맞물리면 '-1'(진정)을 출력하고 그렇지 않으면 '0'(거짓)을 출력합니다.
먼저 b를 9 비트로 비트 시프트 한 다음 a를 1..18 비트만큼 시프트하여 성공적인 도브테일 링을 테스트하는 방식으로 작동합니다 (즉, 오른쪽에서 완전히 왼쪽으로).
a AND b가 0인지 ( '충돌'비트가 없는지) 확인한 다음 A XOR B를 취하고 후행 0을 잘라 내고 x AND (x + 1)가 다음과 같은지 테스트하여 각 위치에서 더브 테일링을 테스트합니다. 0 (2 ^ n-1 = 1 비트 문자열에만 해당됨).
목탄 , 29 바이트
¬⬤α№⭆↨⁺×Ｘ³χ⍘η³×Ｘ³κ⍘賦³⮌⍘λ²01
온라인으로 시도하십시오! XOR을 시도하거나 값을 함께 추가하려고 할 때 다른 답변이 갖는 문제를 방지하는 기본 3에서 더브 테일링하여 작동합니다. 설명:
α (Uppercase alphabet)
¬⬤ No indices match
№ (Non-zero) Count of
01 Literal string `01` in
θ First input
⍘ ³ Converted as if base 3
× Multiplied by
³ Literal 3
Ｘ Raised to power
κ Current index
⁺ Plus
η Second input
⍘ ³ Converted as if base 3
× Multiplied by
³ Literal `3`
Ｘ Raised to power
χ Predefined constant 10
↨ ³ Converted to base 3 as a list
⭆ Map over digits
λ Current digit
⍘ ² Converted to base 2 as a string
⮌ Reversed
Implicitly print
자바 8, 86 83 82 바이트
(a,b)->{int i=18,t;for(a<<=8;--i>0;i=(a&b)>-(t&(t&-t)+t)?i:0,b*=2)t=a|b;return i;}
다른 답변을 반으로 줄이면서 영감을 얻었습니다. @AZTECCO 덕분에 -3 바이트 .
-1 바이트 덕분에 @ceilingcat .
(32 비트) 정수로 입력합니다. -1진실과 0거짓에 대한 출력 .
온라인으로 시도하십시오.
설명:
(a,b)->{ // Method with two integer parameters and boolean return-type
int i=18, // Index-integer, starting at 18
t; // Temp-integer, uninitialized
for(a<<=8; // Bit-shift the first input-integer `a` 8 bits to the left
--i>0 // Loop `i` in the range (18, 0):
; // After every iteration:
i=(a&b) // Get `a` bitwise-AND `b`
< // And check that it's smaller than:
-( // The negative of:
t // `t`
& // Bitwise-AND with:
(t&-t) // `t` bitwise-AND `-t`
+t)// and add `t`
? // If this is truthy:
0 // Change `i` to 0 (which will also stop the loop)
: // Else:
i, // Keep `i` the same
b*=2) // And multiply `b` by 2
t=a|b; // Set `t` to `a` bitwise-OR `b`
return i;} // Return `i` as result (where -1 means we've changed `i` to 0
// manually as truthy output and 0 means the loop has fully
// looped as falsey output)