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

92

Я просматривал код 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. Не стесняйтесь редактировать это.

Мартин
источник
4
На каком языке написан этот сценарий? Есть ли Math.random()возвращать целое число или двойные на [0,1)? Я не думаю, что ваш сценарий (лучшее, что я могу сказать) вообще отражает поставленную вами проблему.
Brick
7
Что такое код c / c ++? Это разные языки.
Флюгер
14
Вы не можете воспроизвести поведение, которое пытаетесь протестировать на JS. Вот почему в выборе языка все только вы. JS не является строго типизированным, и ответ критически зависит от типа переменных в C / C ++. JS - полная чушь, учитывая заданный вами вопрос.
Brick
4
@WeatherVane Это, по сути, псевдокод, использующий имена функций Javascript. Его речь идет о поведении &и +на беззнаковых целых чисел в C и C ++.
Barmar
11
Имейте в виду, что «я написал тестовую программу и получил ответ, который ожидал для всех возможных входных данных» на самом деле не является гарантией того, что что-то будет вести себя так, как вы ожидаете. Неопределенное поведение может быть таким неприятным; давать неожиданные результаты только после того, как вы убедите себя в правильности кода.

Ответы:

78

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

Сначала обратите внимание на личность (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

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

Вирсавия
источник
81
Это математическое доказательство, игнорирующее возможность переполнения. Посмотрим A=0xFFFFFFFF, B=1, C=3. Первое тождество не выполняется. (Переполнение не будет проблемой для беззнаковой арифметики, но это немного другое дело.)
AlexD
4
Фактически, (a + (b & 255)) & 255это то же самое (a + (b % 256)) % N % 256, где, Nна единицу больше максимального значения без знака. (последняя формула предназначена для интерпретации как арифметика математических целых чисел)
17
Математические доказательства, подобные этому, не подходят для доказательства поведения целых чисел на компьютерных архитектурах.
Джек Эйдли
25
@JackAidley: Они уместны, когда все сделано правильно (что не так, из-за пренебрежения учетом переполнения).
3
@Shaz: Это верно в отношении тестового сценария, но не в части заданного вопроса.
21

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

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

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


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

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

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

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

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

промывка
источник
20

Лемма: 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нет.
Барри
источник
17

Да (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 n
  • int продвижение разрешено только в том случае, если intможет представлять все значения исходного типа (§4.5 / 1), поэтому intдолжно иметь по крайней мере 32 бита, вносящие вклад в значение, плюс бит знака.
  • intне может иметь больше значения битов (не считая бит знака) , чем 32, так как иначе дополнение не может переполнения.
Ален
источник
2
Есть много других операций, помимо добавления, когда мусор в старших битах не влияет на результат в младших битах, которые вас интересуют. См. Эти вопросы и ответы о дополнении 2 , которое использует x86 asm в качестве варианта использования, но также применяется к беззнаковые двоичные целые числа в любой ситуации.
Питер Кордес
2
Хотя, конечно, каждый имеет право проголосовать против анонимно, я всегда ценю комментарий как возможность узнать больше.
alain
2
Это, безусловно, самый простой ответ / аргумент для понимания, ИМО. Перенос / заимствование в сложении / вычитании распространяется только от младших битов к старшим (справа налево) в двоичном формате, так же, как и в десятичном. IDK, почему кто-то проголосовал против этого.
Питер Кордес
1
@Bathsheba: CHAR_BIT не обязательно должен быть 8. Но типы без знака в C и C ++ должны вести себя как обычные двоичные целые числа base2 некоторой разрядности. Я думаю, для этого требуется, чтобы UINT_MAX был 2^N-1. (Я забыл, что N может даже не быть кратным CHAR_BIT, но я почти уверен, что стандарт требует, чтобы перенос происходил по модулю некоторой степени 2.) Я думаю, что единственный способ получить странность - это повысить до знаковый шрифт, достаточно широкий, чтобы вместить aили, bно недостаточно широкий, чтобы удерживать его a+bво всех случаях.
Питер Кордес
2
@Bathsheba: да, к счастью, C-as-portable-assembly-language действительно в основном работает с неподписанными типами. Даже преднамеренно враждебная реализация C не может этого изменить. Это только подписанные типы, где все ужасно для действительно переносимых бит-хаков на C, и Deathstation 9000 действительно может сломать ваш код.
Питер Кордес
14

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


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

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

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

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

Ну вот :)


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

Матье М.
источник
1
вы говорите, что это легко сделать с 32-битными значениями, но на самом деле используйте 16-битные ...: D
Вилли Ментцель
1
@WilliMentzel: Это интересное замечание. Сначала я хотел сказать, что если он работает с 16 битами, то он будет работать так же с 32 битами, 64 битами и 128 битами, потому что Стандарт не имеет определенного поведения для разной ширины бит ... однако я вспомнил, что он действительно для битовой ширины меньше, чем у int: маленькие целые числа сначала преобразуются в int(странное правило). Так что мне действительно нужно провести демонстрацию с 32-битными (а затем она расширяется до 64-битных, 128-битных, ...).
Matthieu M.
2
Поскольку вы не можете оценить все (4294967296 - 1) * (4294967296 - 1) возможных результатов, вы как-то уменьшаете? Я считаю, что MAX должен быть (4294967296 - 1), если вы пойдете по этому пути, но он никогда не закончится в течение нашей жизни, как вы сказали ... так что, в конце концов, мы не можем показать равенство в эксперименте, по крайней мере, в таком, как вы описать.
Вилли Ментцель
1
Тестирование этого на одной реализации дополнения до двух не доказывает, что она переносима для знаковой величины или одного дополнения с шириной типа Deathstation 9000. например, узкий беззнаковый тип может быть повышен до 17-битного, intкоторый может представлять все возможные uint16_t, но где a+bможет переполниться. Это проблема только для беззнаковых типов уже int; C требует, чтобы unsignedтипы были двоичными целыми числами, поэтому переход происходит по модулю степени 2
Питер Кордес
1
Согласился с тем, что C слишком портативен сам по себе. Было бы действительно хорошо, если бы они стандартизировали два дополнения, арифметические сдвиги вправо для подписи и способ выполнять арифметические операции со знаком с семантикой упаковки вместо семантики неопределенного поведения для тех случаев, когда вы хотите обернуть. Тогда C снова может быть полезен в качестве портативного ассемблера, а не минного поля благодаря современным оптимизирующим компиляторам, которые делают небезопасным оставлять любое неопределенное поведение (по крайней мере, для вашей целевой платформы. Неопределенное поведение только в реализациях Deathstation 9000 нормально, как и вы указать).
Питер Кордес
4

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

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

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

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

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

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

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

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


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

chqrlie
источник
3
Ваш 2-й подпункт требует, чтобы (1) aменьше, чем int(2), intимеет 32 бита значения (3) a=0xFFFFFFFF. Не все это может быть правдой.
Barry
1
@Barry: Один случай, который, кажется, соответствует требованиям, - это 33-битный int, где есть 32 бита значений и один бит знака.
Бен Фойгт
2

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

Лорен Пехтель
источник
1
Указанный OP: (a и b - 32-разрядные целые числа без знака) . Если intширина не превышает 33 бита, результат будет таким же даже в случае переполнения. Беззнаковая арифметика гарантирует это: результат, который не может быть представлен результирующим целочисленным типом без знака, уменьшается по модулю числа, которое на единицу больше наибольшего значения, которое может быть представлено результирующим типом.
chqrlie
2

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

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

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

Франческо Донди
источник
0

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

Но чтобы на самом деле узаконить это как ответ, ваша первая строка кода говорит, что возьмите последние 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Переполнится, производя ожидаемый результат.

user3728501
источник
Нет, это не так. Математика char происходит как int и char.
Антти Хаапала