| hacker's delight (программистское) |
[июл. 6, 2014|03:21 pm]
Anatoly Vorobey
|
Читаю Hacker's Delight, которая оправдывает свое название. Много трюков с битами, простых и не очень. Кстати, из тех, что попроще, можно настрогать легко разминки для ума. Например, у вас есть два беззнаковых целых числа x,y, и вы хотите вычислить их среднее арифметическое, округленное вниз. Докажите себе в уме, что это равно
x&y + (x^y)>>1
(здесь ^ это xor, конечно. Кстати, та же формула работает для знаковых x,y, только нужно, чтобы >> было арифметическим сдвигом. В Джаве это так и есть автоматически, в C/C++ можно >>1 заменить на /2).
Вы спросите, а зачем это нужно, почему просто не написать (x+y)/2? Ну хотя бы потому, что может случиться переполнение, если числа достаточно большие. А что, это реально мешает в жизни?
И это хороший повод напомнить об истории с багом в алгоритме двоичного поиска в массиве, которую обнаружили и починили в Джаве аж в 2006 году. Вот отличная запись Джоша Блоха об этом. Если вкратце, то вычисляя середину отрезка mid = (low+high)/2 в двоичном поиске, мы получим переполнение, если массив достаточно большой, больше примерно миллиарда элементов, что в наше время 64-битных процессов уже вполне случается. Однако этот код провисел в знаковой книге Programming Pearls, не говоря уж о куче библиотек и других книг, десятки лет, пока кто-то не обратил внимание. Эта история, кстати, поучительна и притом довольно малоизвестна.
Конкретно двоичный поиск починить легче, потому что известно, что low меньше или равно high, и можно просто написать: low + (high-low)/2. Но в случае, когда неизвестно, кто из x,y больше другого, вышеуказанная формула - наверное, самый экономный способ вычислить среднее арифметическое без переполнения. |
|
