Як відомо, в Java немає беззнакових типів. Якщо в Сі ви могли написати unsigned int (char. Long), то в Java так не вийде. Однак нерідко виникає необхідність у виконанні арифметичних операцій саме з числами без знака. На перший погляд здається, що беззнакові типи в принципі-то і не особливо потрібні (подумаєш, MaxInt для чисел зі знаком менше в два рази, якщо потрібні числа більше, я просто візьму long і далі BigInteger). Але основна відмінність насправді не в тому, скільки різних невід'ємних чисел можна покласти в signed або unsigned int, а в тому, як над ними виробляються арифметичні операції і порівняння. Якщо ви працюєте з бінарними протоколами або з двійковій арифметикою, де важливий кожен використовуваний біт, потрібно вміти виконувати всі основні операції в беззнакову режимі. Розглянемо ці операції по порядку:
Перетворення byte в short (int, long)
Звичайний каст (int) myByte виконає розширення до 32 біт зі знаком - це означає, що якщо старший біт байта був встановлений в 1, то результатом буде те ж саме негативне число, але записане в 32-бітному форматі:
0xff -> 0xffffffff (-1)
Часто це не те, чого б ми хотіли. Для того, щоб виконати розширення до 32 біт без знака і отримати 0x000000ff. в Java можна записати:
Порівняння без урахування знака
Для беззнакового порівняння є лаконічна формула:
Для byte, short і long, відповідно, константи будуть 0x80. 0x8000 і 0x8000000000000000L.
Додавання, віднімання і множення
А ось тут приємний сюрприз - ці операції виконуються коректно в будь-якому випадку. Але в виразах необхідно ретельно стежити за тим, щоб операції виконувалися з числами одного типу, так як будь-які неявні перетворення виконуються з розширенням знака, і можуть призводити до результатів, відмінним від очікуваних. Підступність таких багів в тому, що помилковий сценарій може виконуватися дуже рідко.
Розподіл -256 на 256 дасть нам -1. А нам би хотілося, щоб 0xffffff00 / 0x100 давало 0x00ffffff. а не 0xffffffff (-1). Для byte. short і int рішенням буде перехід до числам більшої розрядності:
Але що робити з long. Переходити на BigInteger в таких випадках зазвичай не варіант - занадто повільно. Залишається тільки брати все в свої руки і реалізовувати розподіл вручну. На щастя, все вже вкрадено до нас - в Google Guava є реалізація беззнакового ділення для long. причому досить спритна. Якщо ви не використовуєте цю бібліотеку, найпростіше видерти шматок коду прямо з файлу UnsignedLongs.java:
Щоб код компілювався, доведеться також запозичити реалізацію compare (long, long):
і Longs.compare (long, long) + flip (long):
Побітові зрушення
Щоб остаточно покрити тему про бітових операціях, згадаємо також про ті зрушення. У x86 асемблері є ціла пачка різних команд, які роблять побітові зрушення - SHL, SHR, SAL, SAR, ROR, ROL, RCR, RCL. Останні 4 здійснюють циклічні зрушення, їх еквівалентів в Java немає. А ось логічні і арифметичні зрушення присутні. Логічний зсув (не враховує знака) - SHL (shift left) і SHR (shift right) - реалізується в Java операторами і gt; gt; gt; відповідно. За допомогою логічних зрушень можна швидко виконувати цілочисельні множення і ділення на числа ступеня двійки. Арифметичний зрушення (враховує знак) вправо - SAR - реалізується оператором gt; gt;. Арифметичний зрушення вліво еквівалентний логічному, і тому спеціального оператора для нього немає. Може здатися дивним, що в асемблері є спеціальний опкод для цієї операції, але насправді він робить те ж саме, тобто SAL повністю повторює поведінку SHL, і про це прямо говорить документація від Intel:
The shift arithmetic left (SAL) and shift logical left (SHL) instructions perform the same operation; they shift the bits in the destination operand to the left (toward more significant bit locations). For each shift count, the most significant bit of the destination operand is shifted into the CF flag, and the least significant bit is cleared (see Figure 7-7 in the Intel®64 and IA-32 Architectures Software Developer'sManual, Volume 1 ).
Тобто SAL додали просто для симетрії, з урахуванням того, що для зсуву вправо є поділ на логічний і арифметичний. Ну а Гослінг вирішив не морочитися (і, думається, правильно зробив).
Отже, ми маємо наступне:
a gt; 1; // зрушення вправо з урахуванням знака (еквівалентно поділу на 2) a gt; gt; gt; 1; // зрушення вправо без урахування знака (еквівалентно беззнакову поділу на 2) заключні рекомендації
- При виконанні арифметичних дій, які можуть привести до переповнення в обраній розрядної сітці, потрібно завжди точно представляти, яка область допустимих значень може бути у змінних, і відслідковувати ці інваріанти, розставляючи затвердження (assertions). Наприклад, очевидно, що при множенні двох довільних 32-розрядних беззнакових чисел результат може не поміститися в 32 біта, і якщо вам потрібно уникнути переповнення, потрібно або переконатися, що в цьому місці ніколи не буде ситуації, при якій твір не влазить в 32 біта , або необхідно попередньо конвертувати обидва операнда в long (виконавши
a - 0xffffffffL). Тут, до речі, можна легко припуститися помилки, конвертувати тільки один з операндів. Ні, потрібно конвертувати в long обидва, тому що якщо другий операнд виявиться негативним, він буде неявно перетворений в long з розширенням знака, і результат множення буде неправильним. - Щедро розставляйте дужки у виразах, де використовуються побітові операції. Справа в тому, що пріоритет побітових операторів в Java дещо дивний, і часто поводиться неочевидним чином. Краще додати пару дужок, ніж потім кілька годин шукати важковловимий помилки.
- Якщо вам потрібна константа типу
long, не забудьте додати суфіксLв кінець литерала константи. Якщо цього не зробити, це буде неlong, аint, і при неявному приведення доlongзнову відбудеться неприємне нам розширення зі знаком.
Насправді це така невелика обфускація: правильніше буде Integer.compare (a - 0x80000000, b - 0x80000000) ;. де як би зрозуміло як все працює. Ми переходимо від чисел в інтервалі від 0 до 0xffffffff до часла в інтервалі від 0x80000000 до 0x7ffffff шляхом лінійного зсуву (ми стартуємо з чисел без знака, а результатом є число без знака, але «так можна», тому що в арифметиці «з доповненням до двох »складання і відніманням однаково і для чисел без знака і для чисел зі знаком) - а після цього вже все порівняння нормально можна виробляти.
Подібні ж трюки часто доводиться виробляти працюючи з SSE.
Ну а далі можна помітити що 0x80000000 - це таке особливе число, що його що відняти, що додати, що про XOR'іть - все одно. Не знаю, правда, який сенс в цій обфускаціі.
Скільки ж вам років-то? Побітові операції були швидше в комп'ютерах 70-х років (і то не у всіх)! Уже в 80-ті складання виконувалося з такою ж швидкістю як і побітові операції!
Якщо я його за п'ять секунд придумав, то очевидно, що п'ять секунд. А по-друге, вся подібна магія повинна бути документально підтверджена. Тут навіть по імені функції видно, що вона робить.
Це не більше заплутано ніж Integer.compare (a ^ 0x80000000, b ^ 0x80000000) і вже точно набагато зрозуміліше, ніж той, шматок коду з п'яти функцій, який в статті наведено. Ви уважно подивилися, що саме в статті пропонується використовувати? Чотири процедури, два з яких вельми не очевидні. А вже оптимізація порівнювати ...
Так ви прямо математик, так. Ділимо 9 на 3 і отримуємо ... 4. Це ж просто свято якесь!
P.S. Тільки не треба приводити ще один «ще більш очевидний» варіант. В кінці-кінців доберетеся-таки до чогось подібного гуглових варіанту. З 10й спроби. Я в вас вірю. Але питання «чому всім ідіотам все далеко не так очевидно, як мені» ніби як вже відпав. Чи ні?
Я б ще додав найпершої рекомендацією: Ніколи не використовуйте ніде, крім ретельно локалізованих модулів взаємодії з legacy даними і низькорівневими протоколами.
У бібліотеці javolution є клас Struct для роботи з такого типу даними.
Для якихось виняткових випадків такий метод, можливо, і буде корисним, але я в java швидше віддам перевагу використовувати знакові типи достатньою для зберігання даних розрядності, ніж городити подібні обгортки. Просто тому, що в процесі розробки всі ці танці забудуться, і почнуться чудеса при порівнянні знакових з беззнаковими, «неправильними» операціями і т.д.
Час вказано в тому часовому поясі, який встановлений на вашому телефоні.