57
\$\begingroup\$

Introduction

In number theory, a number is considered evil if there are an even number of 1's in its binary representation. In today's challenge, you will be identifying whether or not a given number is evil.

Challenge

Your job is to write a full program or function which accepts a single, non-negative integer as input and outputs (or returns) whether or not that number is evil.

  • You may output any truthy value if the number is evil, and any falsy value if the number is not evil.
  • You may input and output in any acceptable format.
  • Standard loopholes are disallowed.
  • OEIS sequence A001969 is the sequence containing all evil numbers.
  • Here is a list of the first 10000 evil numbers, for reference (and more test cases!)
  • This question is , so the shorter, the better.
  • Don't be put off by extremely short answers in golfing languages. I encourage you to submit in any language you like.
  • Here are some test cases:

    3 => True
    11 => False
    777 => True
    43 => True
    55 => False
    666 => False
    

The Leaderboard

At the bottom of the page is a stack snippet containing a leaderboard for this question. (Thanks, @MartinEnder)

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

/* Configuration */

var QUESTION_ID = 169724; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 81420; // This should be the user ID of the challenge author.

/* App */

var answers = [],
  answers_hash, answer_ids, answer_page = 1,
  more_answers = true,
  comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function(data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function(data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if (OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    //else console.log(body);
  });

  valid.sort(function(a, b) {
    var aB = a.size,
      bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function(a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
      .replace("{{NAME}}", a.user)
      .replace("{{LANGUAGE}}", a.language)
      .replace("{{SIZE}}", a.size)
      .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>' + lang + '</a>').text();

    languages[lang] = languages[lang] || {
      lang: a.language,
      lang_raw: lang,
      user: a.user,
      size: a.size,
      link: a.link
    };
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function(a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i) {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
      .replace("{{NAME}}", lang.user)
      .replace("{{SIZE}}", lang.size)
      .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 500px;
  float: left;
}

table thead {
  font-weight: bold;
}

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="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution 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>
<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>
<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>

EDIT: I believe this question is not a duplicate of this, because whereas that question is asking to count the number of ones, this question is asking whether the number of ones is even. Although you can accomplish this question by simply counting the bits, there are other approaches too.

\$\endgroup\$
25
  • 2
    \$\begingroup\$ Related (XOR-ing every binary digit is the same as taking the sum modulo-2). \$\endgroup\$ Commented Aug 1, 2018 at 15:25
  • 4
    \$\begingroup\$ Possible duplicate of Count the number of ones in an unsigned 16-bit integer \$\endgroup\$
    – Beta Decay
    Commented Aug 1, 2018 at 17:11
  • 2
    \$\begingroup\$ @BetaDecay but that doesn't work in reverse: i.e. you cannot take all of these answers and remove the mod 2. Therefore, this challenge invites some new methods. \$\endgroup\$ Commented Aug 1, 2018 at 20:29
  • 22
    \$\begingroup\$ I believe that 666 => False should be a test case. \$\endgroup\$ Commented Aug 2, 2018 at 10:38
  • 2
    \$\begingroup\$ Yes, 666 is not evil, but 616 is. More evidence corroborating Papyrus 115! \$\endgroup\$
    – aschepler
    Commented Aug 7, 2018 at 11:41

136 Answers 136

2
\$\begingroup\$

Flobnar, 22 bytes

> +
|\<:
:&%!@
/<2
2 :

Try it online!

<
%!@   Output 1 if the result of `<` is divisible by 2, 0 otherwise...
2

 \    Recursive call:
:&    set current value to input value, or
/<    the previous value divided by 2
2

   :
 > +
:| <  If the current value is 0, return current (0);
 :    otherwise add the current value to the result of recursive call
\$\endgroup\$
1
\$\begingroup\$

Jelly, 4 bytes

BS2ḍ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Yabasic, 81 bytes

Input""n
s$=Bin$(n)
v=1
For i=1To Len(s$)
If Mid$(s$,i,1)="1"Then v=!v Fi
Next
?v

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 7 bytes

§10Σ↨N²

Try it online! Link is to verbose version of code. Explanation:

     N  Input number
    ↨ ² Convert to base 2
   Σ    Sum of digits
§10     Cyclically index into literal string `10`
        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Chip, 22 bytes

 ABCDEFGHe
a{{{{{{{{*f

Try it online!

Chip works in bytes, so each byte of input here is treated independently (which makes for easy test suites). The first byte is ASCII 7 (decimal 55), then 96 -> 99 and 64 -> 67.

This simply XOR's all the input bits, A-H, together (with an extra 1 to invert the result), and sets the low output bit, a, to the outcome. Output bits e and f are also set, making the program output be ASCII 0 for not-evil, and ASCII 1 for evil.

The right-to-left XOR's ({) can be replaced by right-to-left half adders (@) for the same result.

\$\endgroup\$
7
  • \$\begingroup\$ Interesting language. It looks like the input is treated as 7-bit ASCII, so you can probably save 2 bytes by removing H and its corresponding {. \$\endgroup\$
    – Sundar R
    Commented Aug 2, 2018 at 16:16
  • \$\begingroup\$ @sundar Thanks! Input is easily given as ASCII, but it actually just sees raw bytes. Any control characters, or values above 0x7f are had to express in TIO, but they do work just fine. For example, the unicode smile face is treated as the three independent bytes. \$\endgroup\$
    – Phlarx
    Commented Aug 2, 2018 at 16:35
  • \$\begingroup\$ Ah, it looks like the input characters (at least on TIO) are treated as their UTF-8 encoded bytes. Then I guess the non-terminal bytes can have their high bit set. Just curious, since you said "hard to express in TIO", is there a way to input values above 0x7f by themselves on a local interpreter? On TIO it seems possible only as part of a multibyte character (for eg., to enter 0xe4, I have to input 䀀 (UTF-8 bytes 0xe4, 0x80, 0x80) and ignore the last two outputs). \$\endgroup\$
    – Sundar R
    Commented Aug 2, 2018 at 17:08
  • \$\begingroup\$ The input scheme is quite beyond the point of the language, so sorry if this seems like bikeshedding, but it seems like an extended ASCII code like ISO-8859-1 (/Windows 1252) would make more sense for input for this language, making it easier to input byte values and allowing all byte values in input (for eg. I think the current method can't take 255 as input, since bytes with values 245 - 255 are not valid UTF-8 bytes in any character). \$\endgroup\$
    – Sundar R
    Commented Aug 2, 2018 at 17:16
  • \$\begingroup\$ @sundar No worries! The interpreter just uses a binary input stream, so encoding isn't even taken into account. On a command line, for example, I usually do something like printf '\xe4' | ./chip [...], though input direct from a file would work too. ASCII, in the case of this example, is purely an external consideration, a way to provide a specific set of bits in a convenient (if incomplete) way. \$\endgroup\$
    – Phlarx
    Commented Aug 2, 2018 at 18:11
1
\$\begingroup\$

Brachylog, 5 bytes

ḃ+%₂0

Try it online!

Explanation

ḃ       Take the binary representation of the input
 +      Sum the digits
  %₂0   This sum modulo 2 is 0
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 21 bytes

n->1-sumdigits(n,2)%2

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ +1. Beats the faster n->1-hammingweight(n)%2. \$\endgroup\$
    – Charles
    Commented Aug 2, 2018 at 15:05
1
\$\begingroup\$

Haskell, 37 bytes

f n=even.sum$mapM(pure[0,1])[1..n]!!n

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Bash, 97 64 42 39 Bytes

Thanks ilkkachu

(($(bc<<<obase=2\;$1|tr -d 0|wc -c)%2))

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to code-golf! There is quite a lot you can do here to shorten this - dc expressions are generally shorter than bc - returning True/False in a shell return code is OK - no need to do && echo false || echo true. Here is my shell answer. Some good tips here \$\endgroup\$ Commented Aug 2, 2018 at 0:16
  • \$\begingroup\$ @DigitalTrauma: Thanks. I shortened it up some, still not as short as yours though. \$\endgroup\$
    – jesse_b
    Commented Aug 2, 2018 at 14:00
  • \$\begingroup\$ Doesn't that give an inverted return code? (Considering the common shell custom that zero is truthy) You could save one character by escaping just the semicolon, and a couple by replacing the variable with wc -c: (($(bc<<<obase=2\;$1|tr -d 0|wc -c)%2)) (That also changes the return value so it returns 0 for even number of ones). \$\endgroup\$
    – ilkkachu
    Commented Aug 2, 2018 at 19:34
1
\$\begingroup\$

Common Lisp, 30 bytes

(lambda(x)(evenp(logcount x)))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 33 bytes

sub e{pop=~//;$'?$'%2!=e($'/2):1}

Try it online!

Different approach, one byte longer:

sub e{(grep$_[0]&2**$_,0..31)%2^1}
\$\endgroup\$
1
\$\begingroup\$

Befunge-93, 23 bytes

&#2:_v#:/
v#:\+<_
_2%.@

Try it online!

Outputs 1 for non-evil, 0 for evil numbers. Calculates the parity of the sum of n divided by 2 repeatedly.

\$\endgroup\$
1
\$\begingroup\$

><>, 28 22 bytes

-6 bytes thanks to Jo King

:?!v:2%:@-$?:2,
%2l<;n

Code: 22 bytes
Input: put onto the stack using the -v command line argument
Output: 0 means not evil, 1 means evil

Try it online!

Pseudocode

This is a highly abstracted summary of what the program does.
The interpreter puts the input value into n at startup.

l := 1

while n ≠ 0 do:
  m := n mod 2
  if m ≠ 0 then:
    l := l + 1
  n := (n - m) / 2

print l mod 2
\$\endgroup\$
0
1
\$\begingroup\$

EXCEL, 106 bytes

applied Sir Taosique's answer to handle larger numbers.

=ISEVEN(LEN(SUBSTITUTE(DEC2BIN(MOD(QUOTIENT(A1,256^1),256),8)&DEC2BIN(MOD(QUOTIENT(A1,256^0),256),8),0,)))
\$\endgroup\$
1
\$\begingroup\$

perl -E, 39 bytes

say!((unpack"b*",pack I,pop)=~y/1/1/%2)
\$\endgroup\$
0
1
\$\begingroup\$

Rust, 24 bytes

|x:u64|!x.count_ones()%2

Try it online!

\$\endgroup\$
1
\$\begingroup\$

brainfuck, 104 bytes

+>,[++++>-[<->-----],]<[[-[[<]<]++++++++++<]<<[<,+<]++[->>]>,>[<<]>[>]<]<<<+[<[-<<+>>]<]<+[[<]++[->]<]<.

Try it online!

Outputs a null byte for false, 0x1 for true. Uses the convert to binary trick twice, once to get the sum of binary digits and the other to check if that number is even or odd by getting the last binary digit.

\$\endgroup\$
1
\$\begingroup\$

Pyt, 5 4 bytes

Ħ⁺2%

Try it online!

Explanation:

      Implicit input
Ħ     Convert into binary and count the 1s
 ⁺    Increment
  2%  Mod 2
\$\endgroup\$
1
\$\begingroup\$

K (oK), 13 12 bytes

-1 byte thanks to ngn

~2!+/(99#2)\

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 0= -> ~­­­­ \$\endgroup\$
    – ngn
    Commented Oct 24, 2018 at 22:48
1
\$\begingroup\$

PowerShell, 44 bytes

param($n)for(;$n;$n=$n-shr1){$e+=$n%2}1-$e%2

Try it online!

Straightforward counting.

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 55 52 bytes

-3 bytes thanks to @mazzy

1-([Convert]::ToString("$args",2)-replace0).Length%2

Try it online!

Takes input as an integer from a command-line parameter.

\$\endgroup\$
1
1
\$\begingroup\$

Brain-Flak, 76 bytes

{({<([()]{})>{(<([()]{})>)()}{}}<(()[[]]{}){<>([(){}])(<><{}>)}{}>)}<>({}())

Try it online!

Explanation

{
  ({ Divide by two
    <([()]{})>
    {(<([()]{})>)()}{}
  }
  # Invert other side if 1 is the next digit
  <(()[[]]{}){<>([(){}])(<><{}>)}{}>)
}
<>({}()) # Process output
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 29 chars, 58 bytes

{⍵≤0:0⋄∼2∣+/{(2⍴⍨⌊1+2⍟⍵)⊤⍵}⍵}

test:

  f←{⍵≤0:0⋄∼2∣+/{(2⍴⍨⌊1+2⍟⍵)⊤⍵}⍵}
  f 3
1
  f 11
0
  f 777
1
\$\endgroup\$
1
\$\begingroup\$

ink, 53 bytes

=e(n)
~temp o=0
-(i)~o+=n%2
~n=n/2
{n:->i}{1-o%2}->->

Try it online!

Counts bits.

\$\endgroup\$
1
\$\begingroup\$

GolfScript, 13 bytes

2 base{+}*2%!

Try it online!

This can't really be golfed much harder in this language, I don't believe. Maybe a character somewhere? But you absolutely need to use "2 base", and that takes up half the program, which stinks. I did find a second, different solution though -

2 base[1]/,2%

Try it online!

Here's the explanation for both;

2 base        #Convert into binary
#--------------------------#
      {+}*    #Add up all the 1s and 0s
          2%  #Mod 2
            ! #If even, make 1. If odd, make 0.
#--------------------------#
      [1]/    #Divide the binary across the 1s, this leaves 1 more array than the number of 1s
          ,   #Count the off-by-one array
           2% #If it mods to 1, it's even (because off by one), if not, it's 0. Neat!

If I could say "0 is truthy, and 1 is falsy", then I could save a character on the first one, but that would just be silly!

\$\endgroup\$
3
  • \$\begingroup\$ This gives an error for input 0 \$\endgroup\$
    – Pseudo Nym
    Commented Feb 20, 2020 at 21:16
  • \$\begingroup\$ Works fine for me - are you putting it in "input" or "header"? Header is where GS takes in input - straight into the stack. \$\endgroup\$
    – Mathgeek
    Commented Feb 21, 2020 at 13:15
  • \$\begingroup\$ That was the issue. \$\endgroup\$
    – Pseudo Nym
    Commented Feb 21, 2020 at 14:59
1
\$\begingroup\$

05AB1E, 4 bytes

bSOÈ

Explanation:

bS    # Takes the input and coverts it into a list of binary digits
  O   # Sums all of the digits in this list
   È  # Checks if the sum is even

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Exact duplicate of Kevin's answer. \$\endgroup\$
    – Grimmy
    Commented Feb 21, 2020 at 17:19
1
\$\begingroup\$

Python 3, 30 bytes

lambda n:bin(n).count('1')%2<1

Try it online!

Thanks to @Stephen for saving a byte!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ You can save a byte with <1 instead of ==0. \$\endgroup\$
    – Stephen
    Commented Feb 19, 2020 at 20:50
  • 2
    \$\begingroup\$ ...lambda n:~bin(n).count('1')%2 would save one more (still not gonna beat lambda n:int(bin(n),13)%2 though :)) \$\endgroup\$ Commented Feb 20, 2020 at 1:07
  • \$\begingroup\$ You can also do lambda x:~x.bit_count()%2 which is shorter \$\endgroup\$
    – TKirishima
    Commented May 12, 2022 at 22:19
1
\$\begingroup\$

Java, 29 28 26 64 63 49bytes

static boolean c(int r){return r==0||c(r*2)^r<0;}

Try it online!

Seems to work. Nice bit of recursion. It'd be 26 25 23 if I could rename the outer class. Perhaps get a better reference to itself.

Old and boring saves 14 bytes, by Jo King. (If you really want traditional and do-it-by-hand r->0<((r=(r=(r=(r^=r<<16)^r<<8)^r<<4)^r*4)^r*2) for 47 (may have the odd byte of flab).

\$\endgroup\$
1
  • \$\begingroup\$ @JoKing I don't have a knowledge of all the meta posts the rules are covered on. \$\endgroup\$ Commented Feb 21, 2020 at 12:39
1
\$\begingroup\$

C(GCC, clang), 33 bytes

f(n){return!__builtin_parity(n);}

Uses a compiler builtin, and as such works only with GCC and clang and whatever other compiler that implements it. Appears to work with all optimization settings.

Try it online! - GCC

Try it online! - clang

\$\endgroup\$
1
  • \$\begingroup\$ You can abuse GCC's register placement to avoid the return (see this tip): Try it online! \$\endgroup\$
    – pxeger
    Commented Mar 8, 2022 at 7:55
1
\$\begingroup\$

Golfscript, 13 bytes

~2base{},,2%!

Try it online!

~: turn input string into an integer

2base: turn top of stack into base two (represented by an array of 1s and 0s)

{},: filter out all 0s; the , command consumes the array and a code block ({}) and pushes an array containing only the elements for which the codeblock evaluates positivly (the 1s)

,: the top of stack is an array, so , consumes the array and pushes the length of the array

2%!: push 2, get the modulus(%) of the length and 2, and invert(!) the result

when the program halts, the stack is dumped into stdout, this results in either 1 for true or 0 for false

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.