# Generate a parity bit

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.

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>

• Rather annoyingly, o has even parity.
– Neil
Apr 25, 2016 at 23:36
• Can you clarify "Builtins that count the number of "on" bits in a string or character are not allowed." a bit better? What about built-in base conversion? Etc..
– orlp
Apr 25, 2016 at 23:46
• @DrGreenEggsandHamDJ Comments on Stack sites are volatile and subject to disappear without warning for no reason, at any capable user's whim. As a result, it's highly encouraged that specs integral to the challenge be in the post itself, not the comment section.
– cat
Apr 26, 2016 at 2:00
• @cat For example, in python: str(int(s, 2)).count('1')? No, I wouldn't consider that to be a single builtin function that violates that rule. Does my edit make it more clear? Apr 26, 2016 at 2:08
• @cat As far as I'm concerned char == single_char_string. I also edited that into the post. Apr 26, 2016 at 19:10

# MATL, 8 7 bytes

8\hBz2\

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


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

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

• 27030>>((p^p>>4)&15)&1 should calculate the parity of p and is even 1 byte shorter Apr 26, 2016 at 8:51
• The space in char *s is uneeded Apr 26, 2016 at 9:21
• 62 bytes: f(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;} The %3 will always return 0 for a 0, but may return 1 or 2 for a 1. This is acceptable under the rules: truthy if it's a 1 Apr 26, 2016 at 9:29
• 27030>>((p^p>>4)&15)&1. Well, err, obviously. ;-) Apr 26, 2016 at 15:02
• @LevelRiverSt Brilliant! thanks! Apr 26, 2016 at 15:17

## 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',

• Wow, that's a really neat way of handling eo! Apr 27, 2016 at 3:17

## 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!

• I was myself trying to come up with a Jelly answer, but those chaining rules ellude me :-) Apr 26, 2016 at 0:40
• @LuisMendo I'm in the same boat; this is my first Jelly answer after having been trying to learn it for... way too long :P Apr 26, 2016 at 0:41
• That V}... that one was really cool!!! (Dennis is a real golfer) +1 It beat every attempt of mine. Oct 13, 2016 at 12:53

# Python, 58 57 bytes

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

• 53 (Python 2 only): lambda s,p:map(bin,map(ord,s)).count('1')%2^(p>'e') Apr 26, 2016 at 8:02
• You can save a byte with !=p>'e'.
– xnor
Apr 26, 2016 at 8:59
• Wait, my byte-save doesn't actually work because Python treats it as a chained inequality.
– xnor
Apr 26, 2016 at 9:07
• lambda s,p:map(bin,map(ord,p+s))[8:].count('1')%2
– xnor
Apr 26, 2016 at 9:11
– orlp
Apr 26, 2016 at 9:32

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


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

## 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;  # 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  # 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). # JavaScript (ES6), 69 bytes (s,p)=>[...s].map(c=>{for(n=c.charCodeAt();n;n>>=1)r^=n&1},r=p>"e")|r  ## 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  # 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.  # Julia, 584745 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!

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

• Wow, very nice! You can golf off two bytes by using the ² command. This automatically pushes the second input on top of the stack. Also, two-char strings can be shortend using „. So "oe" is equivalent to „. For 13 bytes: €ÇbSOÈ„oe²k<^ :) Apr 27, 2016 at 12:39
• 05AB1E also uses CP-1252 encoding, so each character here is 1 byte :). Apr 27, 2016 at 12:40
• @Adnan: Thanks! Used notepad++ for the bytecount and just assumed that it counted chars :P Apr 27, 2016 at 13:11

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 1s 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. # 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)}


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

# 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


## 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")))


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

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