Generate a parity bit

Question

A parity bit, is one of the simplest forms of a checksum. First, you have to pick the parity, even or odd. Let's say we pick even. Now, we need a message to transmit. Let's say our message is "Foo". This is written in binary as:

01000110 01101111 01101111

Now, we count the total number of 1's in there, which is 15. Since 15 is an odd number, we must add one extra bit to the end of our message, and we will now have an even number of 'on' bits. This last added bit is known as the "parity bit". If we had picked an odd parity for our checksum, we would have to add an extra '0' so that the number of on bits remains odd.

The challenge:

You must write a program or function that determines what the correct parity bit for a string is. Your program must take two inputs:

• A string, s. This is the message that the checksum will be calculated on. This will be restricted to the 95 printable ASCII characters.

• A character or single character string p, that will either be e for even parity, or o for odd parity.

and produce a truthy-falsey value representing the correct parity bit. Truthy if it's a 1, and falsey if it's a 0.

Builtins that count the number of "on" bits in a string or character are not allowed. For example, a function f that does this: f('a') == 3 or f('foo') == 16 is banned. Anything else, such as base conversion, is fair game.

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

This is codegolf, so standard loopholes apply, and the shortest answer in bytes wins.

Leaderboard

var QUESTION_ID=78569,OVERRIDE_USER=31716;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

MATL, 8 7 bytes

8\hBz2\

Try it online! Or verify all test cases at once.

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

Answer 2

Java, 97 bytes

Because, ya know, 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;}

This is a lambda for a BiFunction<String, Character, Boolean>.

e and o appear to be reversed in the return statement because apparently my logic was backwards.

Answer 3

C, 62 bytes

• 12 bytes saved thanks to @LevelRiverSt and @TonHospel.

XOR has the nice property that it can be used to reduce strings down to one char, while preserving parity.

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

Ideone.

Answer 4

Python 2, 51 bytes

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

This is based on an idea of Sp3000 to count 1's in the string representation of the list of character codes in binary rather than summing for each character.

The new trick is to handle e and o in this as well. If e was odd and o even, we could just prepend the parity bit to the string before doing the count (flipping them because '1' is Truthy). Unfortunately, they are not. But, if we remove all but their last two bits, it's now true.

e 0b11001|01
o 0b11011|11 

This is done by removing the first 9 character of the string representation.

['0b11001|01', 

Answer 5

Jelly, 9 8 bytes

OBFSḂ⁼V}

Try it 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

Thanks to Dennis for a byte!

Answer 6

Python, 58 57 bytes

lambda s,p:sum(bin(ord(c)).count("1")for c in s)&1!=p>'e'

Answer 7

Pyth, 12 bytes

q@"oe"sjCz2w

Test suite.

         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

Answer 8

IA-32 machine code, 15 bytes

Hexdump:

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

Assembly code:

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

This is a function that receives its first argument (string) in ecx and second argument (char) in dl. It returns the result in eax, so it's compatible with the fastcall calling convention.

This code bends the rules when it uses the setpo instruction:

Builtins that count the number of "on" bits in a string or character are not allowed

This instruction sets al to the parity bit calculated by the previous instruction - so I have these two nitpicks on the rules:

• It doesn't count the number of "on" bits - it calculates the parity bit directly!
• Technically, it's the previous instruction (xor) that calculates the parity bit. The setpo instruction only moves it to the al register.

These semantic details out of the way, here is the explanation on what the code does.

The representations of the characters are:

'e' = 01100101
'o' = 01101111

If we add 1 to them, they happen to have just the right parity:

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

So we XOR all the characters of the string, initializing al to these values, which gives the answer.

---

The first instruction is movzx eax, dl instead of the more obvious (and shorter) mov al, dl, because I want to have the number 0 in a register (ah in this case) in order to be able to compare it in the right order (0, [ecx] rather than [ecx], 0).

Answer 9

JavaScript (ES6), 84 72 bytes

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

Bit twiddling turned out to be shorter than converting to base 2 and counting 1s.

Answer 10

Perl, 29 bytes

Includes +2 for -p

Run with the input on STDIN as parity character space string, e.g.

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

parity.pl

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

Answer 11

J, 27 bytes

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

Usage

   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

Answer 12

JavaScript (ES6), 69 bytes

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

Answer 13

PowerShell v2+, 91 bytes

_{/me cries in a corner}

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

Yeah ... so, base conversion is not a strong suit for PowerShell. The conversion from input string to binary representation $a|%{[convert]::toString(+$_,2)} is 32 bytes in and of itself ...

Takes input $a and $b, explicitly casting $a as a char-array in the process. We then check whether $b is -equal to o, and -xor that with the other half of the program. For that part, we take the input string $a, pipe it through a loop to convert each letter to binary, -join all those together to form one solid string, and -replace all the 0s with nothing. We then count the .length of that string and take it mod-2 to determine if it's even or odd, which will conveniently be either 0 or 1, perfect for the -xor.

Will return True or False accordingly. See test cases below:

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

Answer 14

Factor, 85 bytes

For some reason I couldn't wrap my head around this one until a few minutes ago, when I simplified (and maybe shortened?) the code.

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

? is like a ternary operator: it tests the truthiness of the third stack item, and either selects the true value or the false value.

It's roughly equivalent to the following C-like pseduocode:

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

The rest of the code is pretty simple:

[                       ! 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.

Answer 15

Julia, 58 47 45 40 bytes

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

This is a function that accepts a string and a character and returns an integer.

To get the number of ones in the binary representation, we first apply the bin function to each character in the string, which gives us an array of binary strings. Then reduce them into one using prod (since * is string concatenation in Julia) and take the set intersection of that string and the character code for 1, which gives us a string of ones. The last index of that string is the number of ones. We XOR this with 1 if the provided character is o and 0 otherwise, then get the parity using bitwise AND 1.

Try it online! (includes all test cases)

Saved 18 bytes thanks to Dennis!

Answer 16

05AB1E, 15, 13 bytes

Code:

€ÇbSOÈ„oe²k<^

Example Input:

Programming Puzzles and Code-Golf
o

Example Output:

1

Explanation:

€                 # 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 È

Thanks to Adnan for saving 2 bytes.

Answer 17

Bash and unix tools (72 bytes)

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

Excepts s as the first and p as the second argument. Fortunately the last 3 bits of o and e has odd and even parity respectively.

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

Supplying the input via <<< adds a line feed character, but the parity of \n is even, so it is not a problem.

Answer 18

Ruby, 57 bytes

If 0 was falsey in Ruby, the == could probably be switched to just -, or there could be other optimizations, but it isn't.

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

Answer 19

Retina, 102 bytes

Takes the string on the first line, and the letter on the second line. Uses ISO 8859-1 encoding.

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

Try it online

The character class on the first line matches any character with an odd number of ones in the binary representation.

Description of how even/odd detection with regex works here.

Answer 20

Octave, 56 bytes

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

The bitunpack function, for ASCII characters, returns them in little-endian order. So by putting the parity flag at the end of our string, unpacking the whole thing, and dropping the last 5 bits, we can then sum up the whole thing mod 2 for our ultimate answer.

Usage:

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

Answer 21

 Common Lisp, 87

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

• Sum the logcount of char-codes of s.
• The remainder of this, when divided by 2, is compared to the position of the parity argument p in the string "oe" (either 0 or 1). For example, if there are 4 ones, the remainder is zero. If p is o, then no additional bit should be added, and the test return false.

Pretty-printed

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

Answer 22

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;}

I did the same as @CAT97, but stripped some characters by using the modulo 8 and concatenate of @Luis Mendo and the use of int instead of boolean.

This is a lambda for a BiFunction<String, Character, Boolean>.

Answer 23

Matlab, 49 bytes

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

where:

• x is the input string;
• p is 'e' for even parity and 'o' for the odd one.

For example:

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

ans =

     0