Generiere ein Paritätsbit

18

Ein Paritätsbit ist eine der einfachsten Formen einer Prüfsumme. Zuerst müssen Sie die gerade oder ungerade Parität auswählen. Nehmen wir an, wir holen gerade. Nun brauchen wir eine Nachricht zum Senden. Angenommen, unsere Nachricht lautet "Foo". Dies ist in binärer Form geschrieben als:

01000110 01101111 01101111

Jetzt zählen wir die Gesamtzahl der darin enthaltenen 1Bits, also 15. Da 15 eine ungerade Zahl ist, müssen wir am Ende unserer Nachricht ein zusätzliches Bit hinzufügen, und es wird nun eine gerade Anzahl von Ein-Bits angezeigt . Dieses zuletzt hinzugefügte Bit ist als "Paritätsbit" bekannt. Wenn wir eine ungerade Parität für unsere Prüfsumme gewählt hätten, müssten wir eine zusätzliche '0' hinzufügen, damit die Anzahl der Ein-Bits ungerade bleibt.

Die Herausforderung:

Sie müssen ein Programm oder eine Funktion schreiben, die das korrekte Paritätsbit für eine Zeichenfolge bestimmt. Ihr Programm muss zwei Eingaben annehmen:

  • Eine Zeichenfolge s. Dies ist die Meldung, für die die Prüfsumme berechnet wird. Dies ist auf die 95 druckbaren ASCII-Zeichen beschränkt.

  • Ein Zeichen oder eine einzelne Zeichenfolge p, die entweder efür gerade Parität oder ofür ungerade Parität steht.

und einen Wahrheits-Falsey- Wert erzeugen , der das korrekte Paritätsbit darstellt. Wahrheit, wenn es eine ist 1, und Falschheit, wenn es eine ist 0.

Builtins, die die Anzahl der Ein-Bits in einer Zeichenfolge oder einem Zeichen zählen, sind nicht zulässig. Zum Beispiel eine Funktion f, die dies tut: f('a') == 3oder f('foo') == 16die gesperrt ist. Alles andere, wie die Basisumwandlung, ist Freiwild.

Test IO:

(without the quotes)
s: "0"
p: 'e'
output: 0

s: "Foo"
p: 'e'
output: 1

s: "Hello World!"
p: 'o'
output: 0

s: "Alex is right"
p: 'e'
output: 1

s: "Programming Puzzles and Code-Golf" 
p: 'e'
output: 0

s: "Programming Puzzles and Code-Golf" 
p: 'o'
output: 1

Dies ist Codegolf, daher gelten Standardlücken, und die kürzeste Antwort in Bytes gewinnt.

Bestenliste

Code-Snippet anzeigen

code-golf string bitwise checksum DJMcMayhem
quelle
10
Ziemlich nervig, ohat eben Parität.
Neil
Können Sie klarstellen, dass "Builtins, die die Anzahl der" Ein "-Bits in einer Zeichenfolge oder einem Zeichen zählen, nicht zulässig sind?" ein bisschen besser? Was ist mit der integrierten Basiskonvertierung? Etc ..
Orlp
@DrGreenEggsandHamDJ Kommentare zu Stack-Sites sind flüchtig und können jederzeit ohne Vorwarnung und ohne Angabe von Gründen entfernt werden. Aus diesem Grund wird dringend empfohlen, dass die für die Herausforderung maßgeblichen Spezifikationen im Beitrag selbst und nicht im Kommentarbereich enthalten sind.
Katze
1
@cat Zum Beispiel in Python: str(int(s, 2)).count('1')? Nein, ich würde das nicht als einzelne eingebaute Funktion betrachten, die gegen diese Regel verstößt. Macht meine Bearbeitung es klarer?
DJMcMayhem
1
@cat Soweit es mich betrifft char == single_char_string. Das habe ich auch in den Beitrag eingearbeitet.
DJMcMayhem

Antworten:

9

MATL , 8 7 Bytes

8\hBz2\

Probieren Sie es online! Oder überprüfen Sie alle Testfälle auf einmal .

8\    % Implicitly take first input ('e' or 'o'), and compute modulo 8. Inputs 'e' and 'o' 
      % give 5 or 7 respectively, which have an even or odd number of `1` bits resp.
h     % Implicitly take second input, and concatenate
B     % Convert to binary. Gives 2D array, with one row for each original entry 
z     % Number of nonzero values in that 2D array
2\    % Modulo 2, i.e. compute parity
Luis Mendo
quelle
9

Java, 97 Bytes

Weil, weißt du, Java.

(s,c)->{boolean e=1>0;for(int i:s.getBytes())while(i>0){if(i%2==1)e=!e;i/=2;}return c=='o'?e:!e;}

Dies ist ein Lambda für a BiFunction<String, Character, Boolean>.

eund oscheinen in der return-Anweisung umgekehrt zu sein, weil anscheinend meine Logik rückwärts war.

CAD97
quelle
5

Python 2, 51 Bytes

lambda s,p:`map(bin,map(ord,p+s))`[9:].count('1')%2

Dies basiert auf der Idee von Sp3000 , Einsen in der Zeichenfolgendarstellung der Liste der Zeichencodes in Binärform zu zählen, anstatt für jedes Zeichen zu summieren.

Der neue Trick ist, damit umzugehen eund odas auch. Wenn eungerade und ogerade war, können wir das Paritätsbit einfach der Zeichenfolge voranstellen, bevor wir die Zählung durchführen (umdrehen, weil '1' Wahrheit ist). Leider sind sie nicht. Aber wenn wir alle bis auf die letzten beiden Bits entfernen, ist es jetzt wahr.

e 0b11001|01
o 0b11011|11

Dies erfolgt durch Entfernen des ersten 9Zeichens der Zeichenfolgendarstellung.

['0b11001|01',
xnor
quelle
Wow, das ist eine sehr ordentliche Art des Umgangs eo!
Sp3000
4

Gelee, 9 8 Bytes

OBFSḂ⁼V}

Probieren Sie es online!

O         convert each character in argument 1 (left arg) to its codepoint (ord)
 B        convert to binary (list of 0s and 1s)
  F       flatten
   S      sum the entire list, giving the number of 1s in the entire string
    Ḃ     mod 2 (take the last bit)
       }  now, with the second (right) argument...
      V   eval with no arguments. This returns...
            1 for e because it expands to 0e0 (i.e., does 0 exist in [0])
            0 for o because it expands to 0o0 (0 OR 0, false OR false, false)
     ⁼    test equality between the two results

Danke an Dennis für ein Byte!

Türknauf
quelle
1
Ich selbst habe versucht, eine Jelly-Antwort zu finden, aber diese Verkettungsregeln sind mir egal :-)
Luis Mendo
2
@ LuisMendo Ich bin im selben Boot; Dies ist meine erste Gelee-Antwort, nachdem ich versucht habe, sie zu lange zu lernen: P
Türklinke
Das V}... das war echt cool !!! (Dennis ist ein echter Golfer) +1 Es hat jeden meiner Versuche geschlagen.
Erik der Outgolfer
4

C 62 Bytes

  • Dank @LevelRiverSt und @TonHospel werden 12 Bytes gespart.

XOR hat die nette Eigenschaft, dass es verwendet werden kann, um Zeichenfolgen auf ein Zeichen zu reduzieren, während die Parität erhalten bleibt.

f(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;}

Ideone.

Digitales Trauma
quelle
1
27030>>((p^p>>4)&15)&1 sollte die Parität von p berechnen und ist sogar 1 Byte kürzer
Ton Hospel
1
Der Platz in char *sist nicht belegt
Ton Hospel
2
62 Bytes: f(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;}Der %3gibt immer 0 für eine 0 zurück, kann aber 1 oder 2 für eine 1 zurückgeben. Dies ist unter den folgenden Regeln akzeptabel:truthy if it's a 1
Level River St
1
27030>>((p^p>>4)&15)&1. Gut ähm, offensichtlich. ;-)
Digital Trauma
@LevelRiverSt Genial! Vielen Dank!
Digital Trauma
4

Python, 58 57 Bytes

lambda s,p:sum(bin(ord(c)).count("1")for c in s)&1!=p>'e'
orlp
quelle
1
53 (nur Python 2):lambda s,p:`map(bin,map(ord,s))`.count('1')%2^(p>'e')
Sp3000
Mit können Sie ein Byte speichern !=p>'e'.
Xnor
Warten Sie, meine Byte-Speicherung funktioniert nicht wirklich, weil Python sie als verkettete Ungleichung behandelt.
XNOR
lambda s,p:`map(bin,map(ord,p+s))`[8:].count('1')%2
Xnor
@xnor Posten Sie einfach Ihre eigene Antwort.
Orlp
3

Pyth, 12 Bytes

q@"oe"sjCz2w

Testsuite.

         z    take a line of input
        C     convert to int
       j  2   convert to base 2, array-wise (so, array of 0s and 1s)
      s       sum (count the number of ones)
 @"oe"        modular index into the string to get either "o" or "e"
q          w  test equality to second line of input
Türknauf
quelle
3

JavaScript (ES6), 84 bis 72 Byte

(s,p)=>(t=p>'e',[...s].map(c=>t^=c.charCodeAt()),t^=t/16,t^=t/4,t^t/2)&1

Das Bit-Twiddling erwies sich als kürzer als das Umwandeln in Basis 2 und das Zählen von 1s.

Neil
quelle
2

Perl, 29 Bytes

Beinhaltet +2 für -p

Führen Sie mit der Eingabe in STDIN eine Paritätszeichenfolge aus, z

parity.pl <<< "p Programming Puzzles and Code-Golf"

parity.pl

#!/usr/bin/perl -p
$_=unpack"B*",$_|b;$_=1&y;1;
Tonne Hospel
quelle
2

J, 27 Bytes

'oe'&i.@[=[:~:/^:2@#:3&u:@]

Verwendung

   f =: 'oe'&i.@[=[:~:/^:2@#:3&u:@]
   'e' f '0'
0
   'e' f 'Foo'
1
   'o' f 'Hello World!'
0
   'e' f 'Alex is right'
1
   'e' f 'Programming Puzzles and Code-Golf'
0
   'o' f 'Programming Puzzles and Code-Golf'
1
Meilen
quelle
1

JavaScript (ES6), 69 Byte

(s,p)=>[...s].map(c=>{for(n=c.charCodeAt();n;n>>=1)r^=n&1},r=p>"e")|r
user81655
quelle
1

PowerShell v2 +, 91 Byte

Ich weine in einer Ecke

param([char[]]$a,$b)$b-eq'o'-xor(-join($a|%{[convert]::toString(+$_,2)})-replace0).length%2

Ja, die Basiskonvertierung ist für PowerShell nicht besonders geeignet. Die Konvertierung von Eingabezeichenfolge in binäre Darstellung $a|%{[convert]::toString(+$_,2)}beträgt 32 Bytes an und für sich ...

Übernimmt Eingaben $aund wandelt sie $bexplizit $ain ein Zeichen-Array um. Wir prüfen dann, ob $bes -eqangebracht ist o, und -xordas mit der anderen Hälfte des Programms. Für diesen Teil nehmen wir die Eingabezeichenfolge $a, leiten sie durch eine Schleife, um jeden Buchstaben in Binär umzuwandeln, -joinalle diese zusammen bilden eine feste Zeichenfolge und -replacealle 0s mit nichts. Wir zählen dann die .lengthdieser Zeichenkette und nehmen Sie es mod-2 , um zu bestimmen , ob es gerade oder ungerade ist , die bequem sein wird , entweder 0oder 1, ideal für die -xor.

Kommt wieder Trueoder Falseentsprechend. Siehe Testfälle unten:

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "0" e
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Foo" e
True

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Hello World!" o
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Alex is right" e
True

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Programming Puzzles and Code-Golf" e
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Programming Puzzles and Code-Golf" o
True
AdmBorkBork
quelle
1

Faktor 85 Bytes

Aus irgendeinem Grund konnte ich meinen Kopf nicht um diesen wickeln, bis ich vor ein paar Minuten den Code vereinfachte (und vielleicht verkürzte?).

[ "e" = [ even? ] [ odd? ] ? [ [ >bin ] { } map-as concat [ 49 = ] count ] dip call ]

?ist wie ein ternärer Operator: Er testet die Richtigkeit des dritten Stapelelements und wählt entweder den trueWert oder den falseWert aus.

Es entspricht in etwa dem folgenden C-ähnlichen Pseudocode:

void* parity_tester_function = strcmp(p, "e") ? (void *) even?  // it's a function pointer (I think)
                                              : (void *) odd? ;

Der Rest des Codes ist ziemlich einfach: 

[                       ! to count a string's set bits:
    [ >bin ] { } map-as ! get the binary of each character, and map as an array, because you can't have stringy data nested in another string (that's called a type error)
    concat              ! { "a" "B" } concat -> "aB"
    [ 49 = ] count      ! count items in the resulting string which match this condition (in this case, the condition we're testing is whether the character has the same code point as "1")
] dip                   ! take the above function pointer off the stack, apply this anonymous function to the now-top of the stack, then restore the value after the quotation finishes.
                        ! in other words, apply this quotation to the second-to-top item on the stack
call                    ! remember that conditionally chosen function pointer? it's on the top of the stack, and the number of sets bits is second.
                        ! we're gonna call either odd? or even? on the number of set bits, and return the same thing it does.
Katze
quelle
1

IA-32 Maschinencode, 15 Bytes

Hexdump:

0f b6 c2 40 32 01 0f 9b c0 3a 21 41 72 f6 c3

Assembler-Code:

    movzx eax, dl;
    inc eax;
repeat:
    xor al, [ecx];
    setpo al;
    cmp ah, [ecx];
    inc ecx;
    jb repeat;
    ret;

Dies ist eine Funktion, die ihr erstes Argument (String) in ecxund ihr zweites Argument (Char) in erhält dl. Es gibt das Ergebnis in zurück eax, sodass es mit der fastcallAufrufkonvention kompatibel ist .

Dieser Code verbiegt die Regeln, wenn er die setpoAnweisung verwendet:

Builtins, die die Anzahl der Ein-Bits in einer Zeichenfolge oder einem Zeichen zählen, sind nicht zulässig

Dieser Befehl setzt alauf das Paritätsbit, das mit dem vorherigen Befehl berechnet wurde. Ich habe also diese beiden Tipps zu den Regeln:

  • Es zählt nicht die Anzahl der "Ein" -Bits - es berechnet das Paritätsbit direkt!
  • Technisch ist es der vorherige Befehl ( xor), der das Paritätsbit berechnet. Der setpoBefehl verschiebt ihn nur in das alRegister.

Diese semantischen Details werden hier erläutert, was der Code bewirkt.

Die Darstellungen der Zeichen sind:

'e' = 01100101
'o' = 01101111

Wenn wir 1 hinzufügen, haben sie zufällig genau die richtige Parität:

'e' + 1 = 01100110 (odd parity)
'o' + 1 = 01110000 (even parity)

Also werden XORalle Zeichen des Strings almit diesen Werten initialisiert , was die Antwort gibt.

Die erste Anweisung ist movzx eax, dlstatt der offensichtlicheren (und kürzeren) mov al, dl, weil ich die Nummer 0 ( ahin diesem Fall) in einem Register haben möchte , um sie in der richtigen Reihenfolge ( 0, [ecx]anstatt [ecx], 0) vergleichen zu können .

anatolyg
quelle
1

Julia, 58 47 45 40 Bytes

f(s,p)=(p>'e')$endof(prod(bin,s)∩49)&1

Dies ist eine Funktion, die eine Zeichenfolge und ein Zeichen akzeptiert und eine Ganzzahl zurückgibt.

Um die Anzahl der Einsen in der Binärdarstellung zu erhalten, wenden wir zuerst die binFunktion auf jedes Zeichen in der Zeichenfolge an, wodurch wir ein Array von Binärzeichenfolgen erhalten. Reduzieren Sie sie dann mit prod(da dies *in Julia die Verkettung von Zeichenfolgen ist) zu einer und nehmen Sie den Schnittpunkt dieser Zeichenfolge mit dem Zeichencode für 1, wodurch wir eine Reihe von Einsen erhalten. Der letzte Index dieser Zeichenfolge ist die Anzahl der Einsen. Wir XOREN dies mit 1, wenn das bereitgestellte Zeichen o und sonst 0 ist, dann erhalten Sie die Parität mit bitweisem AND 1.

Probieren Sie es online! (beinhaltet alle Testfälle)

Dank Dennis 18 Bytes gespart!

Alex A.
quelle
1

05AB1E , 15 , 13 Bytes

Code:

€ÇbSOÈ„oe²k<^

Beispiel Eingabe:

Programming Puzzles and Code-Golf
o

Beispielausgabe:

1

Erläuterung:

€                 # for each char in string
 Ç                # get ascii value
  b               # convert to binary
   S              # split to single chars (ex: '1101' to '1','1','0','1')
    O             # sum
     È            # check if even
      „oe         # push string "oe"
         ²        # push 2nd input (p)
          k       # get 1-based index of p in "oe"
           <      # decrease (to get either 0-based index)
            ^     # xor with result of È

Vielen Dank an Adnan für das Speichern von 2 Bytes.

Emigna
quelle
Wow, sehr nett! Mit dem ²Befehl können Sie zwei Bytes abspulen. Dadurch wird die zweite Eingabe automatisch auf den Stapel gelegt. Zwei-Zeichen-Zeichenfolgen können auch mit gekürzt werden „. Ist "oe"also gleichbedeutend mit „. Für 13 Bytes: €ÇbSOÈ„oe²k<^:)
Adnan
05AB1E verwendet auch die CP-1252- Codierung, sodass jedes Zeichen hier 1 Byte ist :).
Adnan
@Adnan: Danke! Benutzte notepad ++ für das bytecount und nahm gerade an, dass es Zeichen zählte: P
Emigna
0

Ruby, 57 Bytes

Wenn 0in Ruby eine Falschmeldung vorlag, ==könnte die wahrscheinlich auf "nur" umgestellt werden -, oder es könnten andere Optimierungen vorgenommen werden, dies ist jedoch nicht der Fall.

->s,b{s.gsub(/./){$&.ord.to_s 2}.count(?1)%2==(b>?i?0:1)}
Wert Tinte
quelle
0

Netzhaut , 102 Bytes

Nimmt die Zeichenfolge in der ersten Zeile und den Buchstaben in der zweiten Zeile. Verwendet ISO 8859-1-Codierung.

[12478abdghkmnpsuvyzCEFIJLOQRTWX#%&)*,/;=>@[\]^| ](?=.*¶)
1
[^1](?=.*¶)
0
^(0|10*1)*¶o|^0*1(0|10*1)*¶e

Probieren Sie es online aus

Die Zeichenklasse in der ersten Zeile entspricht einem beliebigen Zeichen mit einer ungeraden Anzahl von Einsen in der Binärdarstellung.

Beschreibung, wie gerade / ungerade Erkennung mit Regex hier funktioniert .

mbomb007
quelle
0

Oktave, 56 Bytes

f=@(s,p) mod(sum((i=bitunpack([s p]))(1:length(i)-5)),2)

Die bitunpackFunktion gibt ASCII-Zeichen in Little-Endian-Reihenfolge zurück. Indem wir also das Paritäts-Flag an das Ende unserer Zeichenkette setzen, das Ganze auspacken und die letzten 5 Bits löschen, können wir das Ganze Mod 2 für unsere endgültige Antwort zusammenfassen.

Verwendung:

octave:137> f('Hello World!', 'o')
ans = 0
octave:138> f('Hello World!', 'e')
ans =  1
dcsohl
quelle
0

 Common Lisp, 87

(lambda(s p)(=(mod(reduce'+(mapcar'logcount(map'list'char-code s)))2)(position p"oe")))
  • Addiere die Anzahl der Zeichen von s.
  • Wenn der Rest durch 2 geteilt wird, wird er mit der Position des Paritätsarguments pin der Zeichenfolge verglichen "oe"(entweder 0 oder 1). Wenn es beispielsweise 4 Einsen gibt, ist der Rest Null. Wenn p gleich ist o, sollte kein zusätzliches Bit hinzugefügt werden, und der Test gibt false zurück.

Hübsch bedruckt

(lambda (s p)
  (= (mod (reduce '+ (mapcar 'logcount (map 'list 'char-code s))) 2)
     (position p "oe")))
Core-Dump
quelle
0

Java, 91 Bytes

(s,c)->{s+=c%8;int e=1;for(int i:s.getBytes())while(i>0){if(i%2==1)e^=1;i/=2;}return e==0;}

Ich habe das gleiche getan wie @ CAT97, aber einige Zeichen mit dem Modulo 8 und der Verkettung von @ Luis Mendo und der Verwendung von int anstelle von boolean entfernt.

Dies ist ein Lambda für a BiFunction<String, Character, Boolean>.

Miselico
quelle
0

Matlab, 49 Bytes

f=@(x,p)mod(sum(sum(dec2bin(x)-'0'))+(p-'e'>0),2)

woher:

  • x ist die Eingabezeichenfolge;
  • p ist 'e' für gerade Parität und 'o' für die ungerade.

Beispielsweise:

>> f('Programming Puzzles and Code-Golf','e')

ans =

     0
PieCot
quelle
0

Bash- und Unix-Tools (72 Bytes)

f(){ bc<<<"$(xxd -b<<<"$2$1"|cut -b9-64|tail -c +7|tr -dc 1|wc -c)%2" }

Ausnahmen sals erstes und pals zweites Argument. Glücklicherweise sind die letzten 3 Bits ound ehat jeweils ungerade und gerade Parität.

xxd -b        print the concatenation of `p` and `s` in binary
cut -b9-64    parse xxd output
tail -c +7    keep only the last 3 bits of `p`
tr -dc 1      keep only the `1`s
wc -c         count them
bc ...%2      modulo two

Durch die Eingabe über wird <<<ein Zeilenvorschubzeichen hinzugefügt, die Parität von \nist jedoch gerade, sodass dies kein Problem darstellt.

pgy
quelle