Pristine Bit Checking

Question

Write a program/function that takes two integers in the range \$0\$ to \$255\$ inclusive, and returns whether the binary forms of the numbers are exactly one bit different.

For example, \$1\$ and \$0\$ have binary forms 00000001 and 00000000, which are one bit apart. Similarly, \$152\$ and \$24\$ are 010011000 and 000011000, so they return true.

However, your code must be pristine, such that if any one bit in your program is flipped, it should throw an error. For example, if your program was the single byte a (01100001), then all the 8 possible modified programs:

á ! A q i e c `

must throw an error. Make sure you are modifying by bytes (e.g. the á up there is actually representing the byte \$225\$, not the actual two byte character á).

Test cases:

0,1     => Truthy
1,0     => Truthy
152,24  => Truthy
10,10   => Falsey
10,11   => Truthy
11,12   => Falsey
255,0   => Falsey

Rules:

• Provide a testing framework that can verify that your program is properly pristine, since there will be a lot of possible programs (number of bytes*8), or else a complete proof of pristineness.
  • Please make sure your program is valid before you post it.
• Output needs to be either truthy/falsey (either way around is fine), or else two distinct non-error values
• Errors can be runtime, compiler, interpreter etc.

Answer 1

Python 2, 35 bytes

lambda a,b:(a^b)&-(a^b)in[a^b or[]]

Try it online!

Uses the power-of-two check n&-n==n, eliminating the n==0 false positive.

For reference, these are the pairs of one-char binary operators that are one bit apart, making them hard to use:

+ /
- /
* +
% -
< |
< >

Fortunately, & and ^ are not among these.

Also note that == can become <=, and + can become the comment character #.

---

Python 2, 41 bytes

lambda a,b:bin(a^b).count(`+True`)is+True

Try it online!

Taking TFeld's lambda a,b:bin(a^b).count('1')==1 and making it pristine by changing the 1's to +True and == to is. Thanks to Jo King for 1 byte.

Answer 2

Python 2, 72 67 50 bytes

lambda a,b:sum(map(int,'{:b}'.format(a^b)))is+True

Try it online!

_{-5 bytes, thanks to Jo King}

---

Returns True/False for for truthy/falsey.

The program is basically the same as lambda a,b:bin(a^b).count('1')==1, but without numbers and other chars which work when bit-flipped.

Works by making sure that almost everything is a named function (which are all quite pristine)

The pristine test at the end flips a single bit (for every bit), and tries the function on an input. If that works (correct or not), that variation is printed. No printed programs = pristine function.

Answer 3

Java 8, 68 61 56 45 bytes

a->b->(a.bitCount(a^b)+"").equals(-~(a^a)+"")

-11 bytes thanks to @EmbodimentOfIgnorance, replacing constant java.awt.Font.BOLD with -~(a^a).

Try it online.

Explanation:

The shortest base function would be:

a->b->a.bitCount(a^b)==1

Try it online.

This is modified so there isn't a digit, =, nor one of the +/* operands in it for numeric calculations (so the + for String-concatenation is fine):

The +"" and .equals are to compare by String.equals(String) instead of int==int.
NOTE: Integer.equals(int) could be used here, but would be more bytes, since both the .bitCount and java.awt.Font.BOLD are primitive int instead of Integer-objects, so an additional new Integer(...) would be required to transform one of the two to an Integer-object, before we could use the .equals.

Answer 4

C (gcc), 56 bytes

d(a,b){return(sizeof((char)d))^__builtin_popcount(a^b);}

Try it online!

Returns 0 if the pair differ by 1, non-zero otherwise. Slightly unusual for C, unless you consider it returning EXIT_SUCCESS if the pair differ by 1, any other value otherwise.

Uses sizeof((char)d)) to produce the constant 1 in a pristine way while also forcing the function name to be pristine.

It then XORs that 1 with the popcount of the XOR of the arguments. Luckily the ^ symbol is easy to keep pristine, as is the very long identifier __builtin_popcount.

Meanwhile, here is the script used to test the solution:

#!/bin/bash

SOURCE_FILE=$1
FOOT_FILE=$2
TMP_SRC=temp.c

LENGTH="$(wc -c <"$SOURCE_FILE")"
BITS=$((LENGTH*8))

cat "$SOURCE_FILE" >"$TMP_SRC"
cat "$FOOT_FILE" >>"$TMP_SRC"
if gcc -w $TMP_SRC -o t.out >/dev/null 2>&1; then
    if ./t.out; then
        echo "Candidate solution..."
    else
        echo "Doesn't even work normally..."
        exit
    fi
else
    echo "Doesn't even compile..."
    exit
fi

for i in $(seq 1 $BITS); do
    ./flipbit "$i" <"$SOURCE_FILE" >"$TMP_SRC"
    cat "$FOOT_FILE" >>"$TMP_SRC"
    if gcc -w $TMP_SRC -o t.out >/dev/null 2>&1; then
        echo "Testing flipped bit $i:"
        cat "$TMP_SRC"

        ./t.out >/dev/null 2>&1
        STATUS=$?
        if [ "$STATUS" -eq 0 ]; then
            echo "It works!"
            exit
        elif [ "$STATUS" -eq 1 ]; then
            echo "It doesn't work..."
            exit
        else
            echo "It crashes"
        fi
    fi
done

Which uses the ./flipbit tool I wrote whose source is simply:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int bittoflip = atoi(argv[1]) - 1;
    int ch;

    while ((ch = fgetc(stdin)) != EOF) {
        if (bittoflip < 8 && bittoflip >= 0) {
            putchar(ch ^ (1 << bittoflip));
        } else {
            putchar(ch);
        }

        bittoflip -= 8;
    }

    return 0;
}

The tricky bits were:

• Whitespace: All whitespace (including newlines) have pristine twins that will work similarly
• Comparison: = doesn't work well, since it can be a comparison in every case it could appear. Similarly - doesn't work well. Thus ^ is used to assert equality with 1.
• Variable names: f would clash with b, so had to use d as the function name instead.

Answer 5

R, 38 37 bytes

-1 byte thanks to Nick Kennedy.

dpois(log2(bitwXor(scan(),scan())),T)

Try it online! (Thanks to Giuseppe for setting up the TIO properly.)

Proof that it is pristine (using Nick Kennedy's checker).

Outputs 0 for falsey, and a positive value for truthy, which I understand is acceptable since R will interpret these as False and True.

Explanation: bitwXor(a,b) gives (as an integer) the bitwise XOR between a and b. To check whether it is a power of 2, check whether its log in base 2 is an integer. The function dpois gives the probability density function of the Poisson distribution: its value is 0 for non-integer values, and something positive for non-negative integers. The T is there because dpois requires a second argument (any positive real works, and T is interpreted as 1).

If we insist on outputting to distinct values, the following version outputs FALSE or TRUE in 42 bytes (thanks to Giuseppe for -8 bytes):

dpois(log2(bitwXor(scan(),scan())),T)%in%F

and is also pristine. Try it online!

Answer 6

R, 83 bytes

t(identical(sum(.<-as.double(intToBits(Reduce(bitwXor,scan())))),sum(T^el(.[-T]))))

Try it online!

Proof that this is pristine

Working around the fact that as.integer, as.double etc. are only a bit away from is.integer, is.double etc. was the hardest bit. In the end, using sum(T^el(.[-T]) as a way of both generating a one and checking that as.double has returned a >1 length vector was the best I could do. The wrapping t is to handle the fact that otherwise identical can become ide~tical.

Answer 7

Julia 0.7, 20 bytes

(a,b)->ispow2(a⊻b)

Try it online!

Here is a pristine validator that tries running each modified anonymous function against some input, and neither passes successfully. Note that the code has a multi-byte unicode character, and some possible outputs from bit flipping are not even included, as those produce invalid UTF-8 strings.

Answer 8

C# (Visual C# Interactive Compiler), 37 bytes

a=>b=>a!=b&((a^b)&-(a^b)).Equals(a^b)

The a=>b=> part cannot be changed, or else the function is invalid.

In a!=b, the = cannot be changed since int cannot be converted to bool.

Try it online!

Answer 9

C# (Visual C# Interactive Compiler), 128 101 77 70 61 74 bytes

-27 bytes thanks to Ascii-Only

a=>b=>{var d=Math.Log(a^b,(int)Math.E);return d.Equals((int)Math.Abs(d));}

Try it online!

You have to be quite creative to get numbers in C# without using literals. Only uses ^ operator. Variables a,b are all more than 1 bit away from each other and everything else is a keyword/name.

Answer 10

JavaScript (ES6 in strict mode), 61 bytes

(y,z,e)=>eval(`(y${(e='^=z)*!(y&~-y)')!='^=z)*!(y&~-y)'||e}`)

Try it online! or Make sure that all modified programs are wrong

Answer 11

Groovy, 47 36 bytes

a,b->a.bitCount(a^b).equals(-~(a^a))

Try it online!

Adapted version of Kevin Cruijssen's Java answer.

Answer 12

MATLAB, 37 bytes

@(c,e)eq(nnz(de2bi(bitxor(c,e))),eye)

Sorry, no TIO link, because I can't get the test suite to work under Octave. Thanks @ExpiredData for some helpful comments.

Test suite:

program = '@(c,e)eq(nnz(de2bi(bitxor(c,e))),eye)';
number_of_characters = nnz(program);
success = [];
for character_counter = 0 : number_of_characters
    for bit_no = 1:8
        prog_temp = program;
        if(character_counter > 0)
            prog_temp(character_counter) = bitxor(double(prog_temp(character_counter)),2^(bit_no-1));
        elseif(bit_no<8) % Test the unmodified program once
            continue
        end
        try
            eval(prog_temp);
            eval('ans(2,3)');
            disp(prog_temp)
            success(end+1)=1;   
        catch
            success(end+1)=0;
        end 
    end
end
assert(nnz(success)==1)

Answer 13

Perl 6, 77 43 bytes

Thanks to Jo King for -33 bytes.

{elems(i)eq(sum [+^](@_).polymod(+@_ xx*))}

This is equivalent to

{1 eq(sum [+^](@_).polymod(2 xx*))}

1 was rewritten as elems([""]). 2 was rewritten as sum(elems([""]),elems([""])); elems(["",""]) might seem to work but elems([""-""]) is also valid and seems to hang the tester.

Try it online!

Answer 14

JavaScript (Node.js), 20 bytes

b=>d=>[i=d^b][i--&i]

Try it online!

validator by Arnauld, modified (not use strict)