41
\$\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
  • 14
    \$\begingroup\$ I believe that 666 => False should be a test case. \$\endgroup\$ – user2390246 Aug 2 '18 at 10:38
  • 1
    \$\begingroup\$ @Amphibological I found out why, I'm getting "too many requests from this IP, more requests available in 57696 seconds" back from the Stack Exchange API. I think I know who to blame though. \$\endgroup\$ – Simon Forsberg Aug 5 '18 at 17:04

98 Answers 98

1 2 3
4
0
\$\begingroup\$

Scala, 43 41 bytes

def e(n:Int):Int=if(n>0)n%2^e(n/2)else 1

Test: https://scalafiddle.io/sf/VlU7nun/2

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Could you please add a comma after Scala in the title of your answer so it doesn't break the scoreboard? \$\endgroup\$ – Amphibological Aug 4 '18 at 15:38
0
\$\begingroup\$

CJam, 15 10 bytes

qi2b1e=2%!

Try it online!

Explanation
qi2b1e=2%! %whole code
qi         %Read input as number | Example stack: 10
  2b       %Convert to binary    | Example stack: 1010
    1e=    %Count ones           | Example stack: 22
       2%  %Mod 2                | Example stack: 0
         ! %Invert               | Example stack: 1
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Gol><>, 14 bytes

IW2SD@+$|~2%zh

Try it online!

Explanation:

IW2SD@+$|~2%zh  //Program for reference

I               //Input a integer
 W              //Loop until the number given is 0 (due to the int div 2 inside the loop)
  2SD           //  Push the div and mod of the remaining number by 2
     @          //  Rotate the top three elements on the stack (stack now is: curNumber/2, lastBitSet, bitCount)
      +         //  Add the bit count and the last bit flag
       $|       //  Swap the bitCount with the curNumer/2 and repeat until curNumber/2 == 0
         ~      //Remove the loop exit flag (0) 
          2%zh  //Check wether the bitCount is even, output & exit: 1 == truthy, 0 == falsy
| improve this answer | |
\$\endgroup\$
0
\$\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\$
0
\$\begingroup\$

chevron, 45 bytes

method borrowed from Lynn's python answer.

>:>^n
^n,10,2~x>>^n
b^n,13~x>>^n
^n%2>>^n
>^n

notes:

  • outputs :0 for falsy and :1 for truthy.

  • online interpreter defaults to printing the input at prompts, uncheck "print inp" to disable.

  • replace : with ^__ for no prompt.

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

GolfScript, 14 bytes

2base{^}*!

Try it online!

Explanation:

2base         convert input to binary
     {^}*     xor all bits
         !    flip answer
| improve this answer | |
\$\endgroup\$
0
\$\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

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

Python 3.7, 97 89 76 bytes

def h(s): 
    f=len(bin(s)[2:].replace("0",""))
    if f%2==0:print(f%2==0)

This is my code. I'm just a beginner so don't hate. This code doesn't include the function's argument. That's it.

-11 bytes thanks to Jo King

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm sorry for my naivety. I don't quite understand what you mean. \$\endgroup\$ – Ben Aug 7 '18 at 22:57
  • \$\begingroup\$ There's no indentation before the if and else, so the interpreter will throw an error. For the second part, instead of doing if x: print(True) \n else: print(false), you can just do print(x) \$\endgroup\$ – Jo King Aug 7 '18 at 23:01
  • \$\begingroup\$ But, if I print(s), the output would be the input, which is kind of useless. I can't do otherwise, unless I change the len(bin(s)[2:].replace("0","")) to be a variable, which would only output the number of 1's in the num's binary version. \$\endgroup\$ – Ben Aug 8 '18 at 17:17
  • \$\begingroup\$ I'm not saying print s, I'm saying print the condition of the if statement. In the current code that would be f%2==0. In that case you don't need any variable assignment at all, and it can be just one statement \$\endgroup\$ – Jo King Aug 8 '18 at 21:54
  • \$\begingroup\$ Okay. Now I think I understand. Thanks :) \$\endgroup\$ – Ben Aug 9 '18 at 11:41
1 2 3
4

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