Нетронутая проверка битов

28

Напишите программу / функцию, которая принимает два целых числа в диапазоне от до включительно и возвращает информацию о том, отличаются ли двоичные формы чисел от одного бита.0255

Например, и имеют двоичные формы и , которые находятся на расстоянии одного бита. Аналогично, и равны и , поэтому они возвращают истину.10000000010000000015224010011000000011000

Тем не менее , ваш код должен быть нетронутым , так что если какой-либо бит в вашей программе будет перевернут, он должен выдать ошибку. Например, если ваша программа была одиночной bytea(01100001), то все 8 возможных модифицированных программ:

á ! A q i e c `

должен выбросить ошибку. Удостоверьтесь, что вы модифицируете байтами (например, áнаверху фактически представлен байт , а не фактический двухбайтовый символ )225á

Тестовые случаи:

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

Правила:

  • Предоставьте среду тестирования, которая может проверить правильность вашей программы, поскольку будет много возможных программ (количество байт * 8), или полное доказательство подлинности.
    • Пожалуйста, убедитесь, что ваша программа действительна, прежде чем публиковать ее.
  • Вывод должен быть либо true / falsey (в любом случае это нормально), либо два разных значения без ошибок
  • Ошибки могут быть во время выполнения, компилятор, интерпретатор и т. Д.
Джо Кинг
источник
7
Если кто-то ищет способ генерировать все возможные варианты своего решения, эта программа Japt должна (кто-то, пожалуйста, перепроверить) выполнить свою работу: petershaggynoble.github.io/Japt-Interpreter/…
Shaggy
4
Вот еще один в Python: попробуйте онлайн!
TFeld
Функции не разрешены, так как вы упомянули программу?
Кевин Круйссен
5
@KevinCruijssen Я указал, что функции представления в порядке
Джо Кинг
4
Этот комментарий имеет больше, +1чем большинство моих недавних решений! : \
Лохматый

Ответы:

16

Python 2 , 35 байт

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

Попробуйте онлайн!

Использует проверку степени двойки n&-n==n, устраняя n==0ложные срабатывания.

Для справки: это пары бинарных операторов с одним символом, которые разделены одним битом, что затрудняет их использование:

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

К счастью, &и ^нет среди них.

Также обратите внимание, что ==может стать <=, и +может стать комментарием #.


Python 2 , 41 байт

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

Попробуйте онлайн!

Принимая TFeld - х lambda a,b:bin(a^b).count('1')==1 и делает его нетронутым, изменяя 1, чтобы +Trueи ==в is. Спасибо Джо Кингу за 1 байт.

XNOR
источник
9

Python 2 , 72 67 50 байт

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

Попробуйте онлайн!

-5 байт, спасибо Джо Кингу


Возвращает True/ Falseдля правды / фальси.

Программа в основном такая же lambda a,b:bin(a^b).count('1')==1, но без чисел и других символов, которые работают, когда переворачивается.

Работает, убедившись, что почти все является именованной функцией (которые все довольно нетронуты)

Первоначальный тест в конце переворачивает один бит (для каждого бита) и пробует функцию на входе. Если это работает (правильно или нет), это изменение печатается. Нет печатных программ = нетронутая функция.

TFeld
источник
8

Java 8, 68 61 56 45 байт

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

-11 байт благодаря @EmbodimentOfIgnorance , заменяя константу java.awt.Font.BOLD на -~(a^a).

Попробуйте онлайн.

Объяснение:

Самая короткая базовая функция будет:

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

Попробуйте онлайн.

Это модифицируется, чтобы не было ни цифры, =ни одного из +/*операндов в ней для числовых вычислений (так что +для конкатенации строк это нормально):

+""И .equalsдолжны сравнивать по String.equals(String)а int==int.
ПРИМЕЧАНИЕ: Integer.equals(int)здесь можно использовать, но будет больше байтов, так как оба .bitCountи java.awt.Font.BOLDявляются примитивными, intа не Integer-объектами, поэтому new Integer(...)потребуется дополнительное преобразование одного из двух в Integer-объект, прежде чем мы сможем использовать .equals.

Кевин Круйссен
источник
(int) Math.log (Math.E) составляет 21 байт
действия данных
1
59 байт
Истек срок действия данных
@ExpiredData Спасибо, на самом деле только что нашел более короткую константу java.awt.Font.BOLD, но ваш Objects.equalsхороший гольф, спасибо!
Кевин Круйссен
@ExpiredData На самом деле, Objectsэто часть java.util.импорта, поэтому я должен добавить это к подсчету байтов, я боюсь, делая его 69 байтов .. :(
Кевин Круйссен
3
Будет -~(a^a)работать на 1?
Воплощение невежества
7

C (gcc) , 56 байтов

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

Попробуйте онлайн!

Возвращает, 0если пара отличается на 1, ненулевое значение в противном случае. Немного необычно для C, если только вы не считаете, что он возвращается, EXIT_SUCCESSесли пара отличается на 1, иначе любое другое значение.

Использует sizeof((char)d))для создания константы 1нетронутым способом, а также заставляет имя функции быть нетронутым.

Затем XORs это 1 с поп-счет XOR аргументов. К счастью, ^символ легко сохранить нетронутым, как и очень длинный идентификатор __builtin_popcount.

Между тем вот сценарий, используемый для проверки решения:

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

Который использует ./flipbitинструмент, который я написал, чей источник просто:

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

Хитрые биты были:

  • Пробелы: все пробелы (включая переводы строк) имеют нетронутых близнецов, которые будут работать аналогично
  • Сравнение: =не работает, так как это может быть сравнение в каждом случае, когда оно может появиться. Точно так -же не работает хорошо. Таким образом ^используется для утверждения равенства с 1.
  • Имена переменных: f конфликтует с b, поэтому вместо имени пришлось использовать d в качестве имени функции.
LambdaBeta
источник
Как вы держите ^оператора нетронутым? Если биты на этом были изменены, что мешает ему стать другим оператором? Это все равно будет компилироваться, но просто даст вам неправильный ответ. Я что-то неправильно понимаю о значении слова «нетронутый» здесь?
Коди Грей
4
Если перевернуть только один бит, его ^можно заменить только на какой-либо один _\ZVN~Þили непечатаемый символ в кодовой точке 30. ~Это единственный из тех, который является оператором, но это только унарный оператор.
Несвязанная строка
1
Или даже использовать __LINE__вместо sizeof(char). Я думаю, что можно предположить, что ваша функция будет в строке 1 вашего .c файла. Или даже unixопределяется до 1 на TIO, и, вероятно, большинство других Linux.
Цифровая травма
2
Основная причина для обозначенного размера sizeof заключается в том, что он dзапекается в источнике с наименьшим возможным байтом. В противном случае d(или как вы называете функцию) можно просто изменить, и код все равно будет работать. Даже (__LINE__)с не d();работает, потому что d();может быть изменен на любую другую букву, и он все равно будет компилироваться, так как функция никогда не должна вызываться, поэтому не связана.
LambdaBeta
1
@LambdaBeta Если имя функции изменится, будет ошибка ссылки, даже если d не является самоссылочной. Я думаю, что этого достаточно, лично.
Цифровая травма
7

R , 38 37 байт

-1 байт благодаря Нику Кеннеди.

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

Попробуйте онлайн! (Спасибо Джузеппе за правильную настройку TIO.)

Доказательство того, что это нетронутый (с помощью проверки Ника Кеннеди ).

Выводит 0 для false и положительное значение для truey, что, как я понимаю, является приемлемым, поскольку R будет интерпретировать их как False и True.

Пояснение: bitwXor(a,b)дает (как целое число) побитовый XOR между aи b. Чтобы проверить, является ли оно степенью 2, проверьте, является ли его лог в базе 2 целым числом. Функция dpoisдает функцию плотности вероятности распределения Пуассона: ее значение равно 0 для нецелых значений и что-то положительное для неотрицательных целых чисел. Это Tпотому, что dpoisтребует второго аргумента (любые положительные реальные работы, и Tинтерпретируется как 1).

Если мы настаиваем на выводе в различные значения, следующая версия выводит FALSE или TRUE в 42 байта (спасибо Giuseppe за -8 байтов):

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

и также нетронутый . Попробуйте онлайн!

Робин Райдер
источник
2
Хорошо сделано, получив что-то намного меньшее, чем у меня! Вы можете заменить piна, Tчтобы сохранить байт (все еще нетронутый). Также ваш TIO не соответствует вашему ответу на данный момент.
Ник Кеннеди
@NickKennedy Спасибо! (И спасибо за написание кода, чтобы проверить его нетронутым!). TIO, на который я ссылаюсь, является модифицированной версией, которая проверяет все контрольные примеры. Я добавлю TIO к реальному коду, но я не могу понять, как заставить TIO работать правильно с двумя вызовами scan(); у тебя есть идея? (Код отлично работает на компьютере.)
Робин Райдер
2
@NickKennedy Может быть, что-то подобное? для получения TIO и кода для соответствия?
Джузеппе
@ Джузеппе Замечательно, спасибо!
Робин Райдер
1
ваша вторая версия могла бы использовать Fвместо того exp(-Inf)же, что и у Ника T:-)
Джузеппе
6

R , 83 байта

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

Попробуйте онлайн!

Доказательство того, что это нетронутый

Обойти тот факт, что as.integerи as.doubleт. Д. Только немного от is.integer, is.doubleи т. Д. Было сложнее всего. В конце концов, лучшее, что я мог сделать , это использовать sum(T^el(.[-T])как способ генерации единицы, так и проверку, as.doubleкоторая вернула вектор длины> 1. Упаковка tдолжна справиться с тем, что иначе identicalможет стать ide~tical.

Ник Кеннеди
источник
5

Юлия 0,7 , 20 байт

(a,b)->ispow2(ab)

Попробуйте онлайн!

Вот нетронутый валидатор, который пытается запустить каждую измененную анонимную функцию для некоторого ввода, и ни один из них не проходит успешно Обратите внимание, что код имеет многобайтовый символ Unicode, и некоторые возможные выходные данные от переворачивания битов даже не включены, так как они генерируют недопустимые строки UTF-8.

Кирилл Л.
источник
xи yодин на один, так что я считаю, что это контрпример. yи xтакже 1 бит 9и 6соответственно.
Просроченные данные
Блин, думая о сложных вещах, я совершенно упустил самый простой. Надеюсь, изменение переменных это исправит.
Кирилл Л.
4

C # (интерактивный компилятор Visual C #) , 128 101 77 70 61 74 байта

-27 байт благодаря Ascii-Only

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

Попробуйте онлайн!

Вы должны быть достаточно изобретательны, чтобы получать числа в C # без использования литералов. Использует только оператор ^. Переменные a, b находятся на расстоянии более 1 бита друг от друга, а все остальное является ключевым словом / именем.

Истекшие данные
источник
вам не нужно считать биты - достаточно проверить, что это степень 2 от 1 до 128 включительно
только ASCII
@ Только для ASCII Удачи, проверяя это в разумном количестве байтов, когда мы не можем использовать целые числа ни +/*=для математических, ни для проверочных операций. ;)
Кевин Круйссен
@KevinCruijssen C # также имеет перечисления :(. Damnit
только для ASCII
1
101?
Только для ASCII
1
О_о другой -24. Кстати, вы больше не используете+
только ASCII
3

JavaScript (ES6 в строгом режиме), 61 байт

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

Попробуйте онлайн! или убедитесь, что все измененные программы неверны

Arnauld
источник
О, черт возьми, я не понимал, что я нажал на ссылку кода гольф и увидел этот ответ вне контекста и почти сердечный приступ. Мол, OMG НЕТ
Мари
4
@ Мари Осторожно! Вы можете смотреть на этот код только с сертифицированными очками для гольфа. В противном случае, это может сжечь вашу сетчатку. : p
Арно
1

MATLAB, 37 байт

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

Извините, нет ссылки на TIO, потому что я не могу заставить тестовый набор работать под Octave. Спасибо @ExpiredData за некоторые полезные комментарии.

Тестирование:

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
источник
41 байт
Просроченные данные
@ExpiredData Спасибо за предложение. numelВместо этого я выбрал MATLAB , потому что мой набор тестов не работает в Octave.
Санчизес
Может быть, 38 байт .. не получил лицензию Matlab, но должен работать
Истек срок действия данных
1
@ExpiredData Спасибо, на самом деле можно сделать один байт лучше eye!
Санчизес
1
@ExpiredData Я знаю, я тоже очень раздражен в Октаве. Но использование программы Python в комментариях OP удобно, чтобы увидеть, можете ли вы ввести нового персонажа без проблем.
Санчизес
1

Perl 6 , 77 43 байта

Спасибо Джо Кингу за -33 байта.

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

Это эквивалентно

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

1был переписан как elems([""]). 2был переписан как sum(elems([""]),elems([""])); elems(["",""])Может показаться, что работает, но elems([""-""])также действителен и, кажется, зависает тестер

Попробуйте онлайн!

bb94
источник