((A + (b & 255)) & 255) то же самое, что ((a + b) & 255)?

Я просматривал код C ++ и нашел что-то вроде этого:

(a + (b & 255)) & 255

Двойное И разозлило меня, поэтому я подумал:

(a + b) & 255

( aи bявляются 32-битными целыми числами без знака)

Я быстро написал тестовый скрипт (JS), чтобы подтвердить свою теорию:

for (var i = 0; i < 100; i++) {
    var a = Math.ceil(Math.random() * 0xFFFF),
        b = Math.ceil(Math.random() * 0xFFFF);

    var expr1 = (a + (b & 255)) & 255,
        expr2 = (a + b) & 255;

    if (expr1 != expr2) {
        console.log("Numbers " + a + " and " + b + " mismatch!");
        break;
    }
}

Хотя сценарий подтвердил мою гипотезу (обе операции равны), я до сих пор не доверяю ему, потому что 1) случайный и 2) я не математик, я понятия не имею, что делаю .

Также извините за заголовок Lisp-y. Не стесняйтесь редактировать это.

Они одинаковые. Вот доказательство:

Сначала обратите внимание на личность (A + B) mod C = (A mod C + B mod C) mod C

Давайте еще раз сформулируем проблему, рассматривая ее a & 255как замену a % 256. Это правда, так aкак беззнаковый.

Так (a + (b & 255)) & 255это(a + (b % 256)) % 256

Это то же самое, что и (a % 256 + b % 256 % 256) % 256(я применил указанную выше идентичность: обратите внимание, что modи %эквивалентны для беззнаковых типов.)

Это упрощает то, (a % 256 + b % 256) % 256что становится (a + b) % 256(повторное применение личности). Затем вы можете вернуть побитовый оператор, чтобы получить

(a + b) & 255

завершая доказательство.

При позиционном сложении, вычитании и умножении чисел без знака для получения результатов без знака более значимые цифры ввода не влияют на менее значимые цифры результата. Это применимо как к двоичной арифметике, так и к десятичной арифметике. Это также применимо к знаковой арифметике с дополнением до двух, но не к знаковой арифметике со знаком.

Однако мы должны быть осторожны, беря правила из двоичной арифметики и применяя их к C (я полагаю, что C ++ имеет те же правила, что и C в этом материале, но я не уверен на 100%), потому что арифметика C имеет некоторые загадочные правила, которые могут нас сбить вверх. Беззнаковая арифметика в C подчиняется простым правилам двоичного переноса, но подписанное арифметическое переполнение является неопределенным поведением. Хуже того, при некоторых обстоятельствах C автоматически «продвигает» беззнаковый тип до (подписанного) int.

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

Итак, возвращаясь к формуле в вопросе, эквивалентность зависит от типов операндов.

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

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

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

OTOH, если aи bбыли целыми числами со знаком , размер которых был больше или равен размеру int, то даже в реализациях дополнения до двух есть случаи, когда один оператор был бы четко определен, а другой - неопределенным поведением.

Лемма: a & 255 == a % 256для беззнакового a.

Unsigned aможно переписать в виде m * 0x100 + bнекоторых без знака m, b, 0 <= b < 0xff, 0 <= m <= 0xffffff. Из обоих определений следует, что a & 255 == b == a % 256.

Дополнительно нам понадобятся:

• Распределительное свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n
• математически определение беззнакового сложения: (a + b) ==> (a + b) % (2 ^ 32)

Таким образом:

(a + (b & 255)) & 255 = ((a + (b & 255)) % (2^32)) & 255      // def'n of addition
                      = ((a + (b % 256)) % (2^32)) % 256      // lemma
                      = (a + (b % 256)) % 256                 // because 256 divides (2^32)
                      = ((a % 256) + (b % 256 % 256)) % 256   // Distributive
                      = ((a % 256) + (b % 256)) % 256         // a mod n mod n = a mod n
                      = (a + b) % 256                         // Distributive again
                      = (a + b) & 255                         // lemma

Так что да, это правда. Для 32-битных целых чисел без знака.

А как насчет других целочисленных типов?

• Для 64-битных целых чисел без знака все вышеперечисленное применимо точно так же, просто заменив 2^64на 2^32.
• Для 8- и 16-разрядных целых чисел без знака добавление включает повышение до int. Это intопределенно не будет ни переполнением, ни отрицательным значением ни в одной из этих операций, поэтому все они останутся действительными.
• Для подписанных целых чисел, если либо a+bили a+(b&255)переполнения, это неопределенное поведение. Таким образом, равенство не может выполняться - есть случаи, когда (a+b)&255поведение undefined, но (a+(b&255))&255нет.

Да (a + b) & 255ладно.

Помните сложение в школе? Вы добавляете числа цифру за цифрой и добавляете значение переноса в следующий столбец цифр. Более поздний (более значимый) столбец цифр не может повлиять на уже обработанный столбец. Из-за этого не имеет значения, обнуляете ли вы цифры только в результате или также сначала в аргументе.

Вышесказанное не всегда верно, стандарт C ++ допускает реализацию, которая нарушит это.

Такой Deathstation 9000 : - ) должен был бы использовать 33-битный int, если бы OP имел в виду unsigned short«32-битные целые числа без знака». Если unsigned intэто имелось в виду, DS9K должен был бы использовать 32-битный intи 32-битный unsigned intс битом заполнения. (Целые числа без знака должны иметь тот же размер, что и их подписанные аналоги согласно §3.9.1 / 3, а биты заполнения разрешены в §3.9.1 / 1.) Другие комбинации размеров и битов заполнения также будут работать.

Насколько я могу судить, это единственный способ сломать его, потому что:

• Целочисленное представление должно использовать "чисто двоичную" схему кодирования (§3.9.1 / 7 и сноска), все биты, кроме битов заполнения и знакового бита, должны давать значение 2 ⁿ
• int продвижение разрешено только в том случае, если intможет представлять все значения исходного типа (§4.5 / 1), поэтому intдолжно иметь по крайней мере 32 бита, вносящие вклад в значение, плюс бит знака.
• intне может иметь больше значения битов (не считая бит знака) , чем 32, так как иначе дополнение не может переполнения.

У вас уже есть умный ответ: арифметика без знака - это арифметика по модулю, и поэтому результаты сохранятся, вы можете доказать это математически ...

Однако одна замечательная вещь в компьютерах - это то, что они быстрые. Действительно, они настолько быстры, что перечисление всех допустимых комбинаций из 32 битов возможно за разумный промежуток времени (не пытайтесь использовать 64 бита).

Итак, в вашем случае мне лично нравится просто бросить его в компьютер; Мне нужно меньше времени, чтобы убедить себя в правильности программы, чем убедить себя, что математическое доказательство верно и что я не заметил детали в спецификации ¹ :

#include <iostream>
#include <limits>

int main() {
    std::uint64_t const MAX = std::uint64_t(1) << 32;
    for (std::uint64_t i = 0; i < MAX; ++i) {
        for (std::uint64_t j = 0; j < MAX; ++j) {
            std::uint32_t const a = static_cast<std::uint32_t>(i);
            std::uint32_t const b = static_cast<std::uint32_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

Это перечисляет все возможные значения aи bв 32-битном пространстве и проверяет, выполняется ли равенство или нет. Если это не так, он распечатывает случай, который не сработал, который вы можете использовать в качестве проверки работоспособности.

И, по словам Кланга : равенство сохраняется .

Кроме того, учитывая, что арифметические правила не зависят от разрядности (выше intразрядности), это равенство будет сохраняться для любого беззнакового целочисленного типа размером 32 или более бит, включая 64 и 128 бит.

Примечание. Как компилятор может перечислить все 64-битные шаблоны в разумные сроки? Оно не может. Петли были оптимизированы. В противном случае мы все умерли бы до того, как казнь прекратилась.

Сначала я доказал это только для 16-битных целых чисел без знака; К сожалению, C ++ - безумный язык, в котором intсначала преобразуются небольшие целые числа (с меньшей шириной битов ) int.

#include <iostream>

int main() {
    unsigned const MAX = 65536;
    for (unsigned i = 0; i < MAX; ++i) {
        for (unsigned j = 0; j < MAX; ++j) {
            std::uint16_t const a = static_cast<std::uint16_t>(i);
            std::uint16_t const b = static_cast<std::uint16_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: "
                      << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

И еще раз, по словам Кланга : равенство сохраняется .

Ну вот :)

¹ Конечно, если программа когда-либо непреднамеренно запускает Undefined Behavior, это мало что даст.

Быстрый ответ: оба выражения эквивалентны

• поскольку aи bявляются 32-битными целыми числами без знака, результат будет таким же даже в случае переполнения. Беззнаковая арифметика гарантирует это: результат, который не может быть представлен результирующим целочисленным типом без знака, уменьшается по модулю числа, которое на единицу больше наибольшего значения, которое может быть представлено результирующим типом.

Длинный ответ: не существует известных платформ, на которых эти выражения отличались бы, но Стандарт не гарантирует этого из-за правил комплексного продвижения.

• Если тип aand b(32-битные целые числа без знака) имеет более высокий ранг, чем int, вычисление выполняется как беззнаковое, по модулю 2 ³² , и дает один и тот же определенный результат для обоих выражений для всех значений aи b.

• И наоборот, если тип aи bменьше чем int, оба повышаются, intи вычисление выполняется с использованием знаковой арифметики, где переполнение вызывает неопределенное поведение.

  • Если intимеет как минимум 33 бита значения, ни одно из приведенных выше выражений не может переполняться, поэтому результат точно определен и имеет одинаковое значение для обоих выражений.

  • Если intимеет ровно 32 бита значения, вычисление может переполняться для обоих выражений, например значений a=0xFFFFFFFFиb=1 вызовет переполнение в обоих выражениях. Чтобы этого не произошло, нужно написать ((a & 255) + (b & 255)) & 255.

• Хорошая новость в том, что таких платформ нет. ¹ .

¹ Точнее, такой реальной платформы не существует, но можно настроить DS9K для демонстрации такого поведения и при этом соответствовать стандарту C.

Идентично при условии отсутствия переполнения . Ни одна из версий по-настоящему не защищена от переполнения, но двойная версия более устойчива к нему. Мне неизвестна система, в которой переполнение в этом случае является проблемой, но я вижу, как автор делает это, если таковая имеется.

Да, вы можете доказать это с помощью арифметики, но есть более интуитивный ответ.

При добавлении каждый бит влияет только на более значимые, чем он сам; никогда не менее значимыми.

Следовательно, что бы вы ни делали с старшими битами перед сложением, результат не изменится, пока вы сохраняете только биты менее значимые, чем измененный младший бит.

Доказательство тривиально и оставлено читателю в качестве упражнения.

Но чтобы на самом деле узаконить это как ответ, ваша первая строка кода говорит, что возьмите последние 8 бит b** (все старшие биты bустановлены на ноль) и добавьте это кa а затем возьмите только последние 8 бит настройки результата все выше биты в ноль.

Во второй строке написано добавить aиb взять последние 8 бит, при этом все старшие биты равны нулю.

В результате значимы только последние 8 бит. Поэтому во входных данных значимы только последние 8 бит.

** последние 8 бит = 8 младших битов

Также интересно отметить, что вывод будет эквивалентен

char a = something;
char b = something;
return (unsigned int)(a + b);

Как и выше, значимы только 8 младших unsigned intбитов , но в результате все остальные биты равны нулю. a + bПереполнится, производя ожидаемый результат.