33
\$\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
  • 13
    \$\begingroup\$ I believe that 666 => False should be a test case. \$\endgroup\$ – user2390246 Aug 2 '18 at 10:38
  • 3
    \$\begingroup\$ Leaderboard is broken for me \$\endgroup\$ – Jo King Aug 4 '18 at 2:42

86 Answers 86

35
\$\begingroup\$

Z80 Assembly (8-bit), 2 bytes

The following code only works with values up to 255:

; Input is given in register A.
; P flag is set if A is evil.
B7     or A
C9     ret


16-bit version (works on all test cases), 3 bytes

This works with values up to 65535.

; Input is given in BC.
; Output is the same as above.
78     ld A,B
A9     xor C
C9     ret

If you're feeling adventurous, you can shave off 1 byte by storing the input in A and C like so

      ld BC, 777
C5    push BC
F1    pop AF

and then running

A9    xor C
C9    ret

However, this puts the burden on the caller, so it may be that the two bytes (push BC and pop AF) should be counted as well.

\$\endgroup\$
  • \$\begingroup\$ i like this but how does this work? my memory for assembly (6502 + arm) are that ors are bitwise with 2 operands \$\endgroup\$ – northern-bradley Aug 1 '18 at 20:00
  • 2
    \$\begingroup\$ @northern-bradley On the Z80, it's implied that the second operand of the or mnemonic is the accumulator A. In this case, the command doesn't change A. It only refreshes the status register (and in particular, the parity flag) to reflect the contents of A. \$\endgroup\$ – cschultz2048 Aug 1 '18 at 20:04
  • 1
    \$\begingroup\$ Is P allowed as per codegolf.meta.stackexchange.com/a/8509/29560? It's a single bit within the F (flags) register which has only three pairs of instructions affected by it. Also, this answer fails to mention it's only competing for 8-bit values, since A is an 8-bit register. This means it is unable to give an answer for 777, or any other unsigned value over 255. \$\endgroup\$ – CJ Dennis Aug 3 '18 at 9:51
  • 2
    \$\begingroup\$ Damn built-ins :P \$\endgroup\$ – Jo King Aug 3 '18 at 10:04
  • 1
    \$\begingroup\$ @cschultz2048 A is paired with F, so I wouldn't accept AB or BA as a 16-bit value. BC is 16-bit, but then you need an extra instruction to load one of them into A before XORing the other. I've always just mentioned that my Z80 answers work fully up to 255 or 65535, depending on the question. Maybe add a 16-bit version as well? So 2 bytes for 8-bit values, 3 bytes for 16-bit values. \$\endgroup\$ – CJ Dennis Aug 3 '18 at 13:55
23
\$\begingroup\$

JavaScript (ES6), 18 bytes

f=n=>n?!f(n&~-n):1

Try it online!

Explanation

The bitwise logic goes like this:

  • For integers, ~-n is equivalent to -(-n)-1, so that just another way of doing n-1. In that particular case, we could actually have used n-1.
  • n & (n-1) removes the least significant bit set to 1 in n because decrementing n turns all trailing 0's into 1's and clears the 1 that immediately follows (by carry propagation), while leaving everything else unchanged.

    Example for n = 24 (11000 in binary):

      11000 (24)                  11000 (24)
    -     1                   AND 10111 (23)
    -------                   ---------
    = 10111 (23)              =   10000 (16)
       ^                           ^
       |                           |
       +--- this bit is cleared ---+
    

Therefore, we process as many recursive calls as there are 1's in the binary representation of n, inverting the result each time with !. The last call always returns 1.

Examples:

f(24) = !f(16) = !!f(0) = !!1 = true
f(7) = !f(6) = !!f(4) = !!!f(0) = !!!1 = false
\$\endgroup\$
  • \$\begingroup\$ Hello, I understand what the code does, but I just cannot figure out the logic/reasoning behind it, despite having read several articles about bitwise operations, checking if a number is a power of 2, etc. I know what a recursive function is. I just don't get why it has been used this way and why this works to answer to the puzzle, i.e. the link between the recursion and !f(power of two) <==> evil number. If you have time, explanation would be welcome :) thanks! \$\endgroup\$ – supafly Aug 7 '18 at 15:34
  • 1
    \$\begingroup\$ @supafly I've added an explanation. And BTW: welcome to PPCG! \$\endgroup\$ – Arnauld Aug 7 '18 at 16:09
  • \$\begingroup\$ The processing is very clear now. Still, the idea/reasoning is really magic! Thank you for the explanation! \$\endgroup\$ – supafly Aug 7 '18 at 16:43
13
\$\begingroup\$

Python 2, 25 bytes

lambda n:int(bin(n),13)%2

Try it online!

bin(n) gives a result like '0b10101'. Reading this as a base-13 integer, we get

$$ \color{red}{11\cdot13^5} + 1\cdot13^4 + 0\cdot13^3 + 1\cdot13^2 + 0\cdot13^1 + 1\cdot13^0 $$ which reduces modulo 2 to $$\equiv \color{red}{1 \color{pink}{\cdot 1^5}} + 1 \color{#aaa}{\cdot 1^4} + 0 \color{#aaa}{\cdot 1^3} + 1\color{#aaa}{\cdot 1^2} + 0\color{#aaa}{\cdot 1^1} + 1\color{#aaa}{\cdot 1^0} \pmod 2 $$ $$\equiv \color{red}{1}+1+0+1+0+1 \pmod 2.$$

So int(bin(n),13)%2 equals 1 + (number of ones in bin(n)) modulo 2.

If n is evil, then the result is 1; otherwise it is 0.

I picked up this trick from Noodle9.

\$\endgroup\$
  • \$\begingroup\$ Since this is Python 2, the code can be further shortened with the deprecated repr backtick syntax: lambda n:int(`n`,13)%2. Try it online! \$\endgroup\$ – GarethPW Aug 12 '18 at 23:32
  • \$\begingroup\$ Yeah, had a bit of a brain fart there and forgot the purpose of int’s base argument. Whoops! \$\endgroup\$ – GarethPW Aug 13 '18 at 0:04
11
\$\begingroup\$

Japt -h!, 5 4 3 bytes

¤å^

Try it


Explanation

¤       :Convert to base-2 string
 å^     :Cumulatively reduce by XORing
        :Implicitly output the last element negated
\$\endgroup\$
  • \$\begingroup\$ @LuisfelipeDejesusMunoz, porting Kevin's 05AB1E solution also works out at 5 bytes, if you want to try for that. \$\endgroup\$ – Shaggy Aug 1 '18 at 15:21
  • \$\begingroup\$ ¤¬x v this is kevin's answer \$\endgroup\$ – Luis felipe De jesus Munoz Aug 1 '18 at 15:28
  • \$\begingroup\$ @LuisfelipeDejesusMunoz, yup, that's it. \$\endgroup\$ – Shaggy Aug 1 '18 at 15:28
8
\$\begingroup\$

C# (Visual C# Interactive Compiler), 43 38 bytes


Golfed Try it online!

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

Ungolfed

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

Full code with tests

Func<Int32, Boolean> f = i => Convert.ToString( i, 2 ).Sum( c => c ) % 2 < 1;

Int32[] testCases = { 3, 11, 777, 43, 55 };

foreach( Int32 testCase in testCases ) {
    Console.Write( $" Input: {testCase}\nOutput: {f(testCase)}" );
    Console.WriteLine("\n");
}

Console.ReadLine();

Releases

  • v1.1 - -5 bytes - Replaced Count to Sum
  • v1.0 - 43 bytes - Initial solution.

Notes

  • None
\$\endgroup\$
  • 2
    \$\begingroup\$ Upvoted for the chuckle your "ungolfed" version gave me. \$\endgroup\$ – Jack Brounstein Aug 2 '18 at 17:02
8
\$\begingroup\$

Bash (no external utilities), 56 44 bytes

while(($1));do set $(($1/2)) $(($2+$1%2));done;!(($2%2))

(($1))&&exec $0 $[$1/2] $[$2+$1%2];!(($2%2))

This assumes that the number is found in $1, having been passed as the first command line argument. It also assumes that this is a shell script (so that it can exec itself).

It recurses, after a fashion, using exec $0, until the number (in $1) reaches zero, dividing it by two in each iteration. It also sums (in $2) the number of times we get a number that is odd. At the end, the original number was "evil" if the sum in $2 in not odd.

Example invocations:

$ ./script 3 && echo evil
evil

$ ./script 11 && echo evil

$ ./script 777 && echo evil
evil

$ ./script 43 && echo evil
evil

$ ./script 55 && echo evil

For 0:

$ ./script 0 && echo evil
./script: line 1: ((: %2: syntax error: operand expected (error token is "%2")
evil

Correct result, with a bit of extra on the side.

\$\endgroup\$
7
\$\begingroup\$

R, 37 26 bytes

!sum(scan()%/%2^(0:31))%%2

Try it online!

An alternative to Robert S.'s answer, this eschews the built-in bit splitting but ends up less golfy and thanks to JayCe and digEmAll ends up coming in slightly golfier.

Only works for positive integers less than \$2^{31}-1\$.

\$\endgroup\$
  • \$\begingroup\$ Why don't hardcode 31 instead of log2 ? Try it online! \$\endgroup\$ – digEmAll Aug 1 '18 at 19:04
  • \$\begingroup\$ @digEmAll Which in turn means no need to define x \$\endgroup\$ – JayCe Aug 1 '18 at 19:42
  • \$\begingroup\$ @digEmAll thanks! I wasn't sure about precision issues, although I suppose that past \$2^{31}-1\$ we (probably) lose precision in the %/% and %% operators so it would be a moot point. \$\endgroup\$ – Giuseppe Aug 1 '18 at 19:58
  • \$\begingroup\$ Also intToBits supports only integer values up to 2^31-1 ;) \$\endgroup\$ – digEmAll Aug 1 '18 at 20:19
6
\$\begingroup\$

05AB1E, 4 bytes

bSOÈ

Try it online or verify all test cases.

Explanation:

b       # Convert to binary string
        #  i.e. 777 → 1100001001
 S      # Change it to a list of 0s and 1s
        #  i.e. 1100001001 → ['1','1','0','0','0','0','1','0','0','1']
  O     # Take the sum
        #  i.e. ['1','1','0','0','0','0','1','0','0','1'] → 4
   È    # Check if it's even (1 as truthy, 0 as falsey)
        #  i.e. 4 → 1
\$\endgroup\$
5
\$\begingroup\$

Stax, 4 bytes

:1|e

Run and debug it

:1|e Full program, implicit input-evaluation
:1   Count set bits
  |e Check if even
\$\endgroup\$
5
\$\begingroup\$

R, 99 98 44 34 28 bytes

-1 thanks to Kevin Cruijssen! -54 thanks to ngm! -10 thanks to Giuseppe! -6 thanks to JayCe!

!sum(intToBits(scan())>0)%%2

Try it online!


Alternatively, using the binaryLogic package (39 bytes):

!sum(binaryLogic::as.binary(scan()))%%2
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 24 22 bytes

2∣DigitCount[#,2,1]&

Try it online!

\$\endgroup\$
4
\$\begingroup\$

PHP, 37 36 bytes

<?=1&~substr_count(decbin($argn),1);

To run it:

echo '<input>' | php -nF <filename>

Or Try it online!

Prints 1 for true, and 0 for false.

-1 byte thanks to Benoit Esnard!

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can save one byte by removing the modulo operation: <?=1&~substr_count(decbin($argn),1);. This one also prints 0 for false. \$\endgroup\$ – Benoit Esnard Aug 2 '18 at 11:45
  • \$\begingroup\$ Thanks @BenoitEsnard! That's very clever, I've updated my answer :) You learn something new every day! \$\endgroup\$ – Davіd Aug 2 '18 at 12:09
4
\$\begingroup\$

Brachylog, 4 bytes

ḃo-0

Try it online!

With multiple test cases (😈 is evil and 👼 is not.)

Uses something I discovered recently about the - predicate: its documentation just says "the difference of elements of [input]", but what it actually does is "sum of even-indexed elements (starting from 0th) of input, minus the sum of odd-indexed elements of input".

Here,

converts the number into an array of binary digits,

o sorts them to bring all the 1s together.

Now, if there were an even number of 1s, there would be an equal number of 1s in even indices and odd indices. So the - after that would give a 0. But if there were an odd number of 1s, there would be an extra 1 sticking out, resulting in the difference being either -1 or 1.

So, finally, we assert that the difference is 0, and get a true or false result according to that. With more flexible output requirements, this could be removed for a 3 byte answer, with 0 as truthy output and -1 and 1 as both falsey outputs.

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 36 bytes

c;f(n){for(c=0;n;c++)n&=n-1;n=~c&1;}

Try it online!

Method from K&R https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

Must be compiled with optimization level 0

\$\endgroup\$
  • \$\begingroup\$ Doesn't compile on gcc 5.4.0: error: expected constructor, destructor, or type conversion before '(' token (arrow is pointing at the f in the function name). What compiler flag(s) do I need? \$\endgroup\$ – villapx Aug 1 '18 at 21:52
  • 1
    \$\begingroup\$ Doesn't work with -O. \$\endgroup\$ – nwellnhof Aug 1 '18 at 23:19
  • 2
    \$\begingroup\$ "Returns 0 for truthy, 1 for falsey" Is this legal? Not trying to discredit your answer, just curious, and because it would save me a byte. Note: The word truthy in the question links to this answer. And this comment also mentions truthiness. \$\endgroup\$ – Borka223 Aug 2 '18 at 19:09
  • \$\begingroup\$ @nwellnhof @villapx Compiles fine on my 7.3.0 - just make sure you're not missing the -O0 compiler flag. \$\endgroup\$ – user77406 Aug 2 '18 at 21:02
  • \$\begingroup\$ @Borka223 hmmm after months of perusing this site, I was under the impression that truthy and falsey could be anything, so long as they are consistent within your solution. However, the answer you linked certainly seems to contradict that. I went ahead and added the byte. Thanks \$\endgroup\$ – vazt Aug 2 '18 at 21:54
4
\$\begingroup\$

INTERCAL, 90 65 63 bytes

DOWRITEIN:1
DO:2<-'#0$#65535'~?':1~:1'
DOREADOUT:2
PLEASEGIVEUP

Try it online!

Ungolfed and expanded (for what it's worth) with C style comments.

DO WRITE IN :1 //Store user input in 1
DO :2<-:1~:1 //Select just the ones. So will convert binary 10101 to 111
DO :3<-:?2 //Run the unary xor over the result. Essentially, xor with the right bitshifted
           //(with wraparound) value).
DO :9<-#0$#65535 //Intermingle the 16 bit values of all 0's and all 1's, to create a
                 //32 bit number with 1's in the odd positions.
DO :4<-:9~:3 //It turns out that at this point, evil numbers will have no bits in odd
             //positions, and non-evil numbers will have precisely one bit in an odd
             //position. Therefore, the ~ will return 0 or 1 as appropriate.
PLEASE READ OUT :4 //Politely output
PLEASE GIVE UP //Polite and self explanatory

I had to make a few concessions to make this feasible in INTERCAL. The first is, as with all INTERCAL programs, numerical input must be written out. So if you want to input 707 you would provide SEVEN OH SEVEN.

The second is that INTERCAL doesn't really have proper truthy or falsy value. Instead, it will output the Roman Numeral I (1) if the number is not evil, or a 0 (typically represented as - since Roman Numerals can't normally represent 0).

If you want to flip those so that evil numbers return 1 and non-evil numbers return 0, you can change lines 4 and 5 from the ungolfed version as follows, although it does add 3 bytes.

DO:9<-#65535$#0
DO:4<-#1~:9~3
\$\endgroup\$
3
\$\begingroup\$

Attache, 13 12 bytes

Even@Sum@Bin

Try it online!

(Old 13 bytes: Even@1&`~@Bin)

This is a composition of three functions:

  1. Bin
  2. Sum
  3. Even

This checks that the Sum of the Binary expansion of the input is Even.

\$\endgroup\$
  • \$\begingroup\$ :| i have no words \$\endgroup\$ – ASCII-only Aug 6 '18 at 6:51
  • \$\begingroup\$ @ASCII-only quite succinct, eh? c: \$\endgroup\$ – Conor O'Brien Aug 6 '18 at 6:55
3
\$\begingroup\$

dc, 18 16 bytes

[2~rd1<M+]dsMx2%

Returns (to the stack) 0 for evil and 1 for not evil

Try it online!

Fairly straightforward - recursively applies the combined quotient/remainder operator ~ to the new quotient and adds all the remainders together, then mods by 2 (after spending two bytes to flip to a standard truthy/falsy).

Edited to reflect consensus that 0 for truthy and 1 for falsy is okay, especially in a language that has no sort of if(boolean) construct.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 29 bytes

lambda n:~bin(n).count('1')&1

Try it online!

Returns 1 if True, else 0.

Converts the number to a binary string like '0b11', counts the number of 1s, gets the complement of result, and returns the last bit of the complement (thanks, https://codegolf.stackexchange.com/users/53560/cdlane!) (1 if the original number was even, 0 if it was odd).

\$\endgroup\$
  • 1
    \$\begingroup\$ No fewer bytes but lambda n:~bin(n).count('1')&1 replaces the modular division with something potentially less expensive. \$\endgroup\$ – cdlane Aug 2 '18 at 6:22
3
\$\begingroup\$

x86-16, 3 bytes

NASM listing:

 1                                  parity16:
 2 00000000 30E0                        xor al,ah
 3 00000002 C3                          ret

16-bit integer function arg in AX (which is destroyed), return value in PF.

The hardware calculates the parity of the result for us, in x86's Parity Flag. The caller can use jp / jnp to branch, or whatever they like.

Works exactly like @cschultz's Z80 / 8080 answer; in fact 8086 was designed to make mechanical source-porting from 8080 easy.

Note that PF is only set from the low byte of wider results, so test edi,edi wouldn't work for an x86-64 version. You'd have to horizontal-xor down to 16 bits, or popcnt eax, edi / and al,1 (where 0 is truthy).

\$\endgroup\$
3
\$\begingroup\$

C++ (gcc) (-O0),  36  31 bytes

int f(int i){i=!i||i%2-f(i/2);}

Try it online!


C++ (clang), 35 bytes

int f(int i){return!i||i%2-f(i/2);}

Try it online!


Here is my first attempt at code golfing, hope I didn't break any rule I might have missed.

Edit:
- Saved 5 bytes thanks to @Jonathan Frech : replaced != by - and return by i= (the last replacement does not seem to work with clang though)
- Since there seems to be a debate whether I should use gcc -O0 abuse, I thought I could just give both versions

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! You may be able to save a byte by golfing != to - and another four by golfing return to i=. \$\endgroup\$ – Jonathan Frech Aug 2 '18 at 12:17
  • \$\begingroup\$ @JonathanFrech It's been a long time since I did C++, does it implicitly return the last assigned expression in a function if there's no return statement? I'm guessing it's a gcc thing? \$\endgroup\$ – sundar Aug 2 '18 at 16:26
  • 1
    \$\begingroup\$ It is a gcc specific undefined behaviour abuse on optimization level O0. \$\endgroup\$ – Jonathan Frech Aug 2 '18 at 17:45
  • \$\begingroup\$ By switching to K&R C, you can get it down to 23 bytes (very impressive!) Try it online! \$\endgroup\$ – ErikF Aug 2 '18 at 22:01
  • \$\begingroup\$ @JonathanFrech: why do people insist on using that stupid gcc -O0 hack? It's not like the length of a language's total boilerplate matters much when comparing implementations. Also, it makes it more interesting to choose between return vs. call-by-reference (updating *i in place). I'd rather write C or C++ answers, not un-optimized-gcc-only answers, because un-optimized-gcc isn't a very useful language. \$\endgroup\$ – Peter Cordes Aug 3 '18 at 6:25
2
\$\begingroup\$

Forth (gforth), 53 bytes

: f 1 swap begin 2 /mod -rot xor swap ?dup 0= until ;

Try it online!

Explanation

Takes the xor-sum of the digits of the binary form of the number. (repeatedly divides by 2 and xors the remainder with the "sum" value)

Code Explanation

: f              \ begin a new word definition
  1 swap         \ place 1 on the stack below the input (n)
  begin          \ start an indefinite loop
    2 /mod       \ get the quotient and remainder of dividing n by 2
    -rot         \ move the sum and remainder to the top of the stack
    xor          \ xor the sum and remainder
    swap         \ move the quotient back to the top of the stack
    ?dup         \ duplicate if > 0
    0=           \ get "boolean" indicating if quotient is 0
  until          \ end the loop if it is, otherwise go back to the beginning
;                \ end the word definition
\$\endgroup\$
2
\$\begingroup\$

Java 8, 40 36 bytes

n->n.toString(n,2).chars().sum()%2<1

-4 bytes thanks to @Okx for something I shouldn't have forgotten myself..

Try it online.

Explanation:

n->                // Method with Integer parameter and boolean return-type
  n.toString(n,2)  //  Convert the integer to a binary String
   .chars()        //  Convert that to an IntStream of character-encodings
   .sum()          //  Sum everything together
    %2<1           //  And check if it's even

Note that the character encoding for 0 and 1 are 48 and 49, but summing them and taking modulo-2 still holds the correct results because 48%2 = 0 and 49%2 = 1.

\$\endgroup\$
  • 1
    \$\begingroup\$ n.toString(n,2) saves 4 bytes. \$\endgroup\$ – Okx Aug 1 '18 at 15:55
  • \$\begingroup\$ @Okx Not sure how I forgot about that one, lol.. Thanks! ;) \$\endgroup\$ – Kevin Cruijssen Aug 1 '18 at 17:39
  • \$\begingroup\$ If you're allowed to use 1 and 0 instead of true and false (not sure for Java), you can change to: ~n.toString(n,2).chars().sum()%2 to save one byte. \$\endgroup\$ – Mario Ishac Aug 1 '18 at 19:20
  • 1
    \$\begingroup\$ @MarDev Unfortunately 0 and 1 aren't truthy/falsey in Java, only booleans/Booleans are. If a challenge would state two distinct outputs are allowed the <1 could have been removed to save 2 bytes indeed. :) \$\endgroup\$ – Kevin Cruijssen Aug 1 '18 at 21:02
2
\$\begingroup\$

Perl 6, 21 bytes

*.base(2).comb(~1)%%2

Test it

Expanded:

*\        # WhateverCode lambda (this is the parameter)
.base(2)  # Str representing the binary
.comb(~1) # find the "1"s

%% 2      # is the count of "1"s divisible by 2?
\$\endgroup\$
  • \$\begingroup\$ *.base(2)%9%%2 \$\endgroup\$ – Jo King Aug 1 '18 at 19:56
  • \$\begingroup\$ Ah, that doesn't work for digits with more than 9 bits... \$\endgroup\$ – Jo King Aug 1 '18 at 20:18
  • 1
    \$\begingroup\$ {:3(.base(2))%%2} \$\endgroup\$ – nwellnhof Aug 1 '18 at 22:41
2
\$\begingroup\$

Retina 0.8.2, 28 bytes

.+
$*
+`(1+)\1
$+0
0

11

^$

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

+`(1+)\1
$+0

Partial binary conversion (leaves extra zeroes).

0

Delete all the zeros.

11

Modulo the ones by two.

^$

Test whether the result is zero.

\$\endgroup\$
2
\$\begingroup\$

x86 Assembly, 12 11 bytes

F3 0F B8 44 24 04  popcnt      eax,dword ptr [esp+4] ; Load EAX with the number of ones in arg
F7 D0              not         eax ; One's complement negation of EAX
24 01              and         al,1 ; Isolate bottom bit of EAX
C3                 ret             

-1 byte thanks to @ceilingcat's suggestion

\$\endgroup\$
2
\$\begingroup\$

Bash + GNU utilities, 33

dc -e2o?p|tr -d 0|wc -c|dc -e?2%p

Try it online!

Reads input from STDIN. Outputs 1 for True and 0 for False.

  • dc converts input to a binary string
  • tr removes zeros
  • wc counts remaining ones (and trailing newline, which corrects sense of logic
  • dc calculates count mod 2 and outputs the answer
\$\endgroup\$
2
\$\begingroup\$

Python 2, 28 27 bytes

f=lambda n:n<1or n&1^f(n/2)

Try it online!

Returns a truthy value if exactly one of the ones-bit is a 1 and the result of calling this function on n/2 is truthy is true (or n==0). It works because n/2 is equivalent to a right bitshift with floor division (so Python 2 only).

Alternate version, also 28 27 bytes

g=lambda n:n<1or g(n&n-1)^1

Try it online!

Based on the K&R method of counting set bits referenced by vazt.

Both of these could be two bytes shorter if the output allowed falsey to mean evil.

Edit: Thanks to Amphibological for saving a byte!

\$\endgroup\$
  • \$\begingroup\$ You can remove the spaces between the 1 and the or to save +1 byte. Nice solution! \$\endgroup\$ – Amphibological Aug 2 '18 at 0:22
  • \$\begingroup\$ Man, I thought I tried that. Good catch! \$\endgroup\$ – Jack Brounstein Aug 2 '18 at 2:05
2
\$\begingroup\$

APL (Dyalog Unicode), 10 bytesSBCS

Anonymous tacit function. Can take any array of integers as argument.

≠⌿1⍪2∘⊥⍣¯1

Try it online!

2∘⊥⍣¯1 convert to binary, using as many digits as needed by the largest number, separate digits along primary axis

1⍪ prepend ones along the primary axis

≠⌿ XOR reduction along the primary axis

\$\endgroup\$
2
\$\begingroup\$

J, 9 bytes

Anonymous tacit function. Can take any integer array as argument.

1-2|1#.#:

Try it online!

1- one minus (i.e. logical negation of)

2| the mod-2 of

1#. the sum (lit. the base-1 evaluation) of

#: the binary representation

\$\endgroup\$
  • \$\begingroup\$ Nice one! the boring approach is 9 bytes: 2|1+1#.#: \$\endgroup\$ – Conor O'Brien Aug 1 '18 at 21:21
  • \$\begingroup\$ This only seems to work because 777 in the input makes every number be represented in 10 bits. Replace it with e.g. 480 and the output flips. \$\endgroup\$ – FrownyFrog Aug 1 '18 at 22:45
  • \$\begingroup\$ @ConorO'Brien Boring trumps incorrect. \$\endgroup\$ – Adám Aug 2 '18 at 7:43
  • \$\begingroup\$ @FrownyFrog Fixed. \$\endgroup\$ – Adám Aug 2 '18 at 7:43
2
\$\begingroup\$

C#, 65 bytes

So I'm terrible at codegolf, but here's my hacky string + LINQ solution:

n=>{return Convert.ToString(n,2).Where(c=>c=='1').Count()%2==0;};

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ A few tips: .Where(c=>c=='1') you can save 1 byte by comparing if c is bigger than '0', and you can save another byte by changing '0' to the decimal representation 48. One more byte can be saved on .Count()%2==0 by comparing if the result is less than 1, resulting in this solution: n=>{return Convert.ToString(n,2).Where(c=>c>48).Count()%2<1;}; \$\endgroup\$ – auhmaan Aug 2 '18 at 16:13
  • 2
    \$\begingroup\$ Also, you can save more 8 bytes by moving the predicate from Where to Count and removing the Where completely. Your solution would end up like this n=>{return Convert.ToString(n,2).Count(c=>c>48)%2<1;}; for a total of 54 bytes. \$\endgroup\$ – auhmaan Aug 2 '18 at 16:14

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.