43
\$\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\$
  • 2
    \$\begingroup\$ Related (XOR-ing every binary digit is the same as taking the sum modulo-2). \$\endgroup\$ – Kevin Cruijssen Aug 1 '18 at 15:25
  • 4
    \$\begingroup\$ Possible duplicate of Count the number of ones in an unsigned 16-bit integer \$\endgroup\$ – Beta Decay Aug 1 '18 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\$ – Amphibological Aug 1 '18 at 20:29
  • 16
    \$\begingroup\$ I believe that 666 => False should be a test case. \$\endgroup\$ – user2390246 Aug 2 '18 at 10:38
  • 2
    \$\begingroup\$ Yes, 666 is not evil, but 616 is. More evidence corroborating Papyrus 115! \$\endgroup\$ – aschepler Aug 7 '18 at 11:41

104 Answers 104

1
\$\begingroup\$

perl -E, 39 bytes

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

Rust, 24 bytes

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

Try it online!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

K (oK), 13 12 bytes

-1 byte thanks to ngn

~2!+/(99#2)\

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 0= -> ~­­­­ \$\endgroup\$ – ngn Oct 24 '18 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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Brain-Flak, 76 bytes

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

Try it online!

Explanation

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

Regex (ECMAScript), 37 33 bytes

Edit: Down 4 bytes thanks to Neil's idea of subtracting the least-significant two bits instead of the most-significant two bits.

^(((?=(((x*)(?=\5$))*))\3x){2})*$

Try it online!

^
(
    # Subtract the two least-significant "1" bits as
    # they would be in tail's binary representation.
    (
        # Divide tail evenly by 2 as many times as we can, atomically
        (?=
            (((x*)(?=\5$))*)
        )\3
        x                # Subtract a 1 bit
    ){2}
)*                       # Loop as many times as possible...
$                        # and only match if the final result is 0.

The PCRE version of this is especially concise at 26 bytes: ^((((x*)(?=\4$))*+x){2})*$

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ ^((((.*)(?=\4$))*.(.*)(?=\5$)){2})*$ is only 36 bytes. \$\endgroup\$ – Neil Feb 5 '19 at 10:34
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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Forth (gforth), 41 bytes

: f 1 swap 63 for 0 d2* m+ next + 2 mod ;

Try it online!

A function with signature ( u -- 0-or-1 ), that is, one that takes a cell-sized integer from the stack and gives a 0 (not evil) or 1 (evil) on the stack. gforth's native boolean is -1 (true) and 0 (false), but any nonzero value is recognized as true, just like many other languages.

Unlike the answer to a very similar challenge, the FP trick seems to fail to save bytes here.

How it works

: f ( u -- 0-or-1 ) \ Declare function f
  1 swap 63 for     \ Store a 1 under u, and loop 64 times ( 1 u )
                    \ The 1 is bit-count + 1
    0               \   Push a 0 (i.e. cast to unsigned double-cell int)
    d2*             \   Shift double-cell int left once ( 1 u' 0-or-1 )
                    \   In effect, shift MSB of u into the top
    m+              \   Add double [1 u'] and single [0-or-1]
                    \   In effect, add the bit to the bit-count
  next              \ End loop ( bc+1 0 )
  + 2 mod           \ Remove the dummy 0 at the top, and take modulo 2
;
| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This gives an error for input 0 \$\endgroup\$ – Pseudo Nym Feb 20 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 Feb 21 at 13:15
  • \$\begingroup\$ That was the issue. \$\endgroup\$ – Pseudo Nym Feb 21 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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 3, 30 bytes

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

Try it online!

Thanks to @Stephen for saving a byte!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You can save a byte with <1 instead of ==0. \$\endgroup\$ – Stephen Feb 19 at 20:50
  • \$\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\$ – Jonathan Allan Feb 20 at 1:07
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).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @JoKing I don't have a knowledge of all the meta posts the rules are covered on. \$\endgroup\$ – Tom Hawtin - tackline Feb 21 at 12:39
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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Scala, 24 bytes

_.toBinaryString.sum%2<1

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\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!

| improve this answer | |
\$\endgroup\$
0
\$\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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Stacked, 15 bytes

[bits sum 2%0=]

Try it online!

Checks whether or not the sum of the bits of the input mod 2 (2%) is 0 (0=).

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

C# (.NET Core), 58 bytes

n=>System.Convert.ToString(n,2).Replace("0","").Length%2<1

Try it online!

I could do something similar to the Java answer with

n=>System.Convert.ToString(n,2).Sum(c=>c)%2<1

That's 45 bytes but then I would need to add another 18 for using System.Linq;. So I needed to find another approach.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Red, 57 bytes

func[n][s: on until[if n % 2 = 1[s: not s]1 > n: n / 2]s]

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Julia 0.6, 20 bytes

n->count_ones(n)%2<1

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

dc, 27 bytes

0sb[2~lb+sbd1<a]dsaxlb1++2%

Try it online!

Instead of accumulating the bits in register b, we can also leave them on the stack (replace lb+sb by r) which essentially converts the input to binary, push 1, sum the stack and do the mod 2. But it's the same byte-count:

[2~rd1<a]dsax1[+z1<a]dsax2%

Try it online!

Explanation

Register b = 0, divmod on ToS, add remainder to b and loop until ToS is less or equal to 1, then compute ToS + b + 1 mod 2:

0sb[2~lb+sbd1<a]dsaxlb1++2%  # example input 5                     |  stack
0sb                          # initialize register b with 0        |  5
   [2~lb+sbd1<a]             # push the string [..]                |  [2~lb+sbd1<a]
                dsa          # duplicate & store it to register a  |  [2~lb+sbd1<a]
                   x         # execute the string*                 |  1
                    lb       # push register b                     |  1 1
                      1+     # increment by 1                      |  2 1
                        +    # add                                 |  3
                         2%  # modulo 2                            |  1

# Recursively called string:
2~lb+sbd1<a  # recursively called string   |  5
2~           # divmod 2                    |  1 2
  lb         # push register b             |  0 1 2
    +        # add                         |  1 2
     sb      # store register b            |  2
       d     # duplicate                   |  2 2
        1<   # if top (popped) is > 1:
          a  # | execute register a        |  2
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

SAS, 35 bytes

e=1-mod(count(put(i,binary.),1),2);

This expression takes a variable i as input and populates the result in a new variable, e. It relies on implicit conversion from character to numeric when specifying which digit to count.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Python 3, 69 53 39 bytes

print(bin(int(input())).count('1')%2<1)

Works by using the built in python binary to converter, bin(), on the input, then counts the number of ones in there, checks if it is equal to 0 mod 2, and prints the result (outputs True/False).

Probably needs some more golfing, but this was my first whirl.

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can't assume inputs preassigned to a variable, though you can use a lambda: lambda x:1if len([i for i in bin(x)[2:]if i=='0'])%2==0else 0 which is shorter anyways (I included some basic golfing). \$\endgroup\$ – ბიმო Aug 2 '18 at 19:25
  • \$\begingroup\$ Some more golfing on your approach (using that b has a higher ascii-codepoint than '0') leaves you with: lambda x:len([1for i in bin(x)if'0'<i])%2 \$\endgroup\$ – ბიმო Aug 2 '18 at 19:31
  • \$\begingroup\$ @OMᗺ you should probably post that as your own answer, as it's such a better approach than mine. I'd feel bad taking credit for it =) \$\endgroup\$ – heather Aug 2 '18 at 19:56
  • \$\begingroup\$ I won't - there are already shorter ones, but your submission still uses a preassigned variable as input which is not allowed. \$\endgroup\$ – ბიმო Aug 2 '18 at 20:17
  • \$\begingroup\$ @OMᗺ fixed by switching to input() \$\endgroup\$ – heather Aug 2 '18 at 20:24
0
\$\begingroup\$

Math++, 40 bytes

?>a
3+3*!a>$
b+a%2>b
_(a/2)>a
2>$
!(b%2)
| improve this answer | |
\$\endgroup\$
0
\$\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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Python 2, 46 bytes

lambda n:sum(int(d)for d in str(bin(n))[2:])%2

Outputs 1 for True or 0 for false

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You don't need to stringify the binary \$\endgroup\$ – Jo King Aug 7 '18 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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