Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

hacker's delight (программистское)

Читаю 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 больше другого, вышеуказанная формула - наверное, самый экономный способ вычислить среднее арифметическое без переполнения.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments