Pristine Bit Checking

28

Schreiben Sie ein Programm / eine Funktion, die zwei Ganzzahlen im Bereich von 0 bis einschließlich 255 akzeptiert und zurückgibt, ob die Binärformen der Zahlen genau ein Bit unterschiedlich sind.

Beispielsweise haben 1 und 0 Binärformen 00000001und 00000000, die ein Bit voneinander entfernt sind. In ähnlicher Weise 152 und 24 sind 010011000und 000011000, so sie wahr zurück.

Allerdings müssen SieCode sein pristine , so dasswenn jemand etwas in Ihrem Programm gekippt wird, sollte es einen Fehler aus. Wenn Ihr Programm beispielsweise das einzelne Bytea(01100001) ist, dann sind alle 8 möglichen geänderten Programme:

á ! A q i e c `

muss einen Fehler werfen. Vergewissern Sie sich, dass Sie eine Änderung nach Bytes vornehmen (z. B. árepräsentiert das obere Byte tatsächlich das Byte 225 und nicht das tatsächliche Zwei-Byte-Zeichen á).

Testfälle:

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

Regeln:

  • Stellen Sie ein Testframework bereit, mit dem Sie überprüfen können, ob Ihr Programm einwandfrei ist, da es eine Vielzahl möglicher Programme gibt (Anzahl der Bytes * 8) oder einen vollständigen Beweis der Unverfälschtheit.
    • Bitte stellen Sie sicher, dass Ihr Programm gültig ist, bevor Sie es veröffentlichen.
  • Die Ausgabe muss entweder wahrheitsgetreu / falsch sein (beides ist in Ordnung), oder es müssen zwei unterschiedliche fehlerfreie Werte angegeben werden
  • Fehler können Laufzeit, Compiler, Interpreter etc. sein.
Scherzen
quelle
7
Wenn jemand der Suche nach einer Möglichkeit , alle möglichen Variationen ihrer Lösung zu erzeugen, das Japt Programm sollte tun (jemand überprüfen bitte) , um den Job: petershaggynoble.github.io/Japt-Interpreter/...
Shaggy
4
Hier ist auch eine in Python: Probieren Sie es online aus!
TFeld
Funktionen sind nicht erlaubt, da Sie das Programm erwähnt haben?
Kevin Cruijssen
5
@ KevinCruijssen Ich habe angegeben, dass Funktionsübermittlungen in Ordnung sind
Jo King
4
Dieser Kommentar enthält mehr +1als die meisten meiner jüngsten Lösungen! : \
Shaggy

Antworten:

16

Python 2 , 35 Bytes

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

Probieren Sie es online!

Verwendet die Zweierpotenzprüfung n&-n==n, um das n==0falsche Positiv zu eliminieren .

Als Referenz sind dies die Paare von Ein-Zeichen-Binäroperatoren, die ein Bit voneinander entfernt sind, was ihre Verwendung schwierig macht:

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

Zum Glück &und ^gehören nicht dazu.

Beachten Sie auch , dass ==werden kann <=, und +kann das Kommentarzeichen geworden #.


Python 2 , 41 Bytes

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

Probieren Sie es online!

Unter TFeld ist lambda a,b:bin(a^b).count('1')==1 und macht es unberührten durch die 1'en an sich ändernde +Trueund ==zu is. Danke an Jo King für 1 Byte.

xnor
quelle
9

Python 2 , 72 67 50 Bytes

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

Probieren Sie es online!

-5 Bytes, danke an Jo King


Returns True/ Falsefor für Wahrhaftige / Falsche.

Das Programm ist im Grunde dasselbe wie lambda a,b:bin(a^b).count('1')==1, jedoch ohne Zahlen und andere Zeichen, die beim Bit-Flippen funktionieren.

Stellt sicher, dass fast alles eine benannte Funktion ist (die alle recht makellos sind)

Der makellose Test am Ende kippt ein einzelnes Bit (für jedes Bit) und probiert die Funktion an einem Eingang aus. Ob das funktioniert (richtig oder nicht), wird diese Variante gedruckt. Keine gedruckten Programme = makellose Funktion.

TFeld
quelle
8

Java 8, 68 61 56 45 Bytes

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

-11 Bytes dank @EmbodimentOfIgnorance , Ersetzen der Konstante java.awt.Font.BOLD durch -~(a^a).

Probieren Sie es online aus.

Erläuterung:

Die kürzeste Basisfunktion wäre:

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

Probieren Sie es online aus.

Dies wurde so geändert, dass weder eine Ziffer =noch eine der Ziffern vorhanden ist+/* Operanden für numerische Berechnungen gibt (also die+ Zeichenfolgenverkettung in Ordnung):

Die +""und .equalssind zu vergleichen durch String.equals(String)statt int==int.
ANMERKUNG: Integer.equals(int)könnte hier verwendet werden, wäre aber mehr Bytes, da sowohl das .bitCountals java.awt.Font.BOLDauch primitiv intanstelle von Integer-Objekten sind, so dass ein zusätzliches new Integer(...)erforderlich wäre, um eines der beiden in ein Integer-Objekt zu transformieren , bevor wir das verwenden könnten .equals.

Kevin Cruijssen
quelle
(int) Math.log (Math.E) ist 21 Byte
Abgelaufene Daten
1
59 Bytes
Abgelaufene Daten
@ExpiredData Danke, habe gerade eine kürzere Konstante mit gefunden java.awt.Font.BOLD, aber deine Objects.equalsist ein schöner Golf, danke!
Kevin Cruijssen
@ExpiredData Ist eigentlich ObjectsTeil des java.util.Imports, also muss ich das zu der Anzahl der Bytes hinzufügen, die ich fürchte, so dass es 69 Bytes sind .. :(
Kevin Cruijssen
3
Würde -~(a^a)für 1 arbeiten?
Verkörperung der Ignoranz
7

C (gcc) , 56 Bytes

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

Probieren Sie es online!

Gibt zurück, 0wenn sich das Paar um 1 unterscheidet, andernfalls ungleich Null. Etwas ungewöhnlich für C, es sei denn, Sie betrachten es als wiederkehrendEXIT_SUCCESS wenn sich das Paar um 1 unterscheidet, oder einen anderen Wert.

Wird verwendet sizeof((char)d)), um die Konstante 1auf makellose Weise zu erzeugen , während gleichzeitig der Funktionsname auf makellose Weise erzwungen wird.

Es wird dann das 1 mit dem Popcount des XOR der Argumente XORs. Glücklicherweise ist das ^Symbol einfach makellos zu halten, ebenso wie der sehr lange Bezeichner __builtin_popcount.

In der Zwischenzeit wird das folgende Skript zum Testen der Lösung verwendet:

#!/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

Welches verwendet das ./flipbitTool, das ich geschrieben habe, dessen Quelle einfach ist:

#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;
}

Die kniffligen Teile waren:

  • Leerzeichen: Alle Leerzeichen (einschließlich Zeilenumbrüche) haben makellose Zwillinge, die ähnlich funktionieren
  • Vergleich: =funktioniert nicht gut, da es sich in jedem Fall um einen Vergleich handeln kann. Ebenso -funktioniert das nicht gut. Somit^ is used to assert equality with 1.
  • Variablennamen: f kollidierte mit b und musste stattdessen d als Funktionsname verwenden.
LambdaBeta
quelle
Wie halten Sie den ^Bediener sauber? Wenn die Bits darauf geändert wurden, was hindert es daran, ein anderer Operator zu werden? Dies würde immer noch kompilieren, aber nur die falsche Antwort geben. Missverstehe ich hier etwas über die Bedeutung des Wortes "makellos"?
Cody Grey
4
Wenn Sie nur ein Bit spiegeln , ^können _\ZVN~ÞSie am Codepunkt 30 ~nur eines oder das nicht druckbare Zeichen ändern. Dies ist der einzige Operator, bei dem es sich jedoch nur um einen unären Operator handelt.
Nicht verwandte
1
Or even use __LINE__ instead of sizeof(char). I think its fine to assume that your function will be on line 1 of your .c file. Or even unix is defined to 1 on TIO, and probably most other Linux.
Digital Trauma
2
The main reason for the char-casted sizeof is to get d baked into the source in the fewest bytes possible. Otherwise d (or whatever you name the function) can just be changed and the code will still work. Even (__LINE__) with d(); wont work because d(); can be changed to any other letter and it will still compile since the function never has to be called, thus isn't linked.
LambdaBeta
1
@LambdaBeta If the name of the function changes, then there will be a link error, even if d is not self-referential. I think this is sufficient, personally.
Digital Trauma
7

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!

Robin Ryder
quelle
2
Well done on getting something so much smaller than mine! You could replace pi with T to save a byte (still pristine). Also your TIO doesn’t correspond to your answer at the moment.
Nick Kennedy
@NickKennedy Thanks! (And thanks for writing the code to check it is pristine!). The TIO I linked to is a modified version that checks all the test cases. I'll add a TIO to the actual code, but I can't figure out how to get TIO to run properly with two calls to scan(); do you have an idea? (The code works fine on a computer.)
Robin Ryder
2
@NickKennedy Maybe something like this? for getting the TIO and the code to match?
Giuseppe
@Giuseppe Wonderful, thanks!
Robin Ryder
1
your second version could use F instead of exp(-Inf), along the same lines as Nick's T :-)
Giuseppe
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.

Nick Kennedy
quelle
5

Julia 0.7, 20 bytes

(a,b)->ispow2(ab)

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.

Kirill L.
quelle
x and y are one bit apart, so I believe this is a counter example. y and x are also 1 bit off 9 and 6 respectively.
Expired Data
Damn, while thinking about complex things, I absolutely missed the simplest one. Hopefully, changing the variables will fix it.
Kirill L.
5

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!

Embodiment of Ignorance
quelle
4

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.

Expired Data
quelle
you don't need to count bits - checking if it's a power of 2 between 1 and 128 inclusive is enough
ASCII-only
@ASCII-only Good luck checking that in a reasonable number of bytes when we can't use integers nor +/*= for mathematical or validating operations. ;)
Kevin Cruijssen
@KevinCruijssen C# has enums too :(. damnit
ASCII-only
1
101?
ASCII-only
1
O_o another -24. btw you no longer use +
ASCII-only
3

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

Arnauld
quelle
Oh my gosh I didnt realize I clicked a code golf link and saw this answer out of context and almost had a heart attack. Like, OMG NO
Marie
4
@Marie Caution! You can only stare at this code with certified golf glasses. Otherwise, it may burn your retina. :p
Arnauld
1

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)
Sanchises
quelle
41 bytes
Expired Data
@ExpiredData Thanks for the suggestion. I went for a MATLAB numel instead, because my test suite does not seem to be working in Octave.
Sanchises
38 bytes maybe.. not got a matlab license but should work
Expired Data
1
@ExpiredData Thanks, one can actually do one byte better with eye!
Sanchises
1
@ExpiredData I know, I'm very annoyed at Octave too. But using the Python program in the OP comments is handy to see if you can introduce a new character without problems.
Sanchises
1

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!

bb94
quelle