Який варіант краще використовувати для поділу целочисленного числа на 2?

Який з наступних методів є найкращим варіантом для поділу цілого на 2 і чому?

Техніка 1:

 x = x >> 1; 

Техніка 2:

 x = x / 2; 

Тут x - ціле число.

386
21 мая '12 в 10:54 2012-05-21 10:54 заданий Abhineet 21 травня '12 о 10:54 2012-05-21 10:54
@ 23 відповідей

Використовуйте операцію, яка найкраще описує те, що ви намагаєтеся зробити.

  • Якщо ви обробляєте число як послідовність біт, використовуйте біт-брейк.
  • Якщо ви розглядаєте його як числове значення, використовуйте поділ.

Зверніть увагу, що вони не зовсім еквівалентні. Вони можуть давати різні результати для негативних цілих чисел. наприклад:

 -5 / 2 = -2 -5 >> 1 = -3 

(ідеон)

834
21 мая '12 в 10:57 2012-05-21 10:57 відповідь дан Mark Byers 21 травня '12 о 10:57 2012-05-21 10:57

Перший виглядає як поділ? Ні. Якщо ви хочете розділити, використовуйте x / 2 . Компілятор може оптимізувати його для використання біт-зсуву, якщо це можливо (це називається скороченням сили), що робить його марною мікро-оптимізацією, якщо ви зробите це самостійно.

border=0
222
21 мая '12 в 10:56 2012-05-21 10:56 відповідь дан Cat Plus Plus 21 травня '12 о 10:56 2012-05-21 10:56

Щоб звалити: є багато причин, щоб використовувати x = x / 2; Ось деякі з них:

  • він більш чітко висловлює ваші наміри (припускаючи, що ви не маєте справу з битами бітів біт або чогось ще)

  • компілятор все одно зменшить це до операції перемикання

  • навіть якщо компілятор не зменшила його і вибрав більш повільну операцію, ніж зрушення, ймовірність того, що це в кінцевому підсумку вплине на продуктивність вашої програми піддається вимірюванню, сама зникає незначно (і якщо вона дійсно впливає на неї, то у вас є фактична причина використовувати зсув)

  • якщо розподіл буде частиною більшого виразу, ви, швидше за все, отримаєте пріоритет правильно, якщо ви використовуєте оператор ділення:

     x = x / 2 + 5; x = x >> 1 + 5; // not the same as above 
  • підписана арифметика може ускладнити ситуацію навіть більше, ніж згадана вище проблема пріоритету

  • щоб повторити - компілятор вже зробить це для вас в будь-якому випадку. Фактично, він перетворює поділ на константу в серію зрушень, додає і примножує на всі види чисел, а не тільки на дві. Див. Це питання для посилань на додаткову інформацію про це.

Коротше кажучи, ви нічого не купуєте, кодуючи зрушення, коли ви дійсно хочете помножити або розділити, за винятком, можливо, зрослої можливості введення помилки. Це була ціла життя, оскільки компілятори не були достатньо розумні, щоб оптимізувати такі речі до зміщення, коли це необхідно.

186
21 мая '12 в 11:34 2012-05-21 11:34 відповідь дан Michael Burr 21 травня '12 о 11:34 2012-05-21 11:34

Який з них є кращим варіантом і чому для поділу целочисленного числа на 2?

Залежить від того, що ви маєте на увазі під кращим.

Якщо ви хочете, щоб ваші колеги ненавиділи вас або щоб ваш код сильно читався, я б обов'язково пішов з першим варіантом.

Якщо ви хочете розділити число на 2, перейдіть до другого.

Ці два не еквівалентні, вони не ведуть себе однаково, якщо число негативне або всередині більших виразів - бітдвіг має більш низький пріоритет, ніж + або - , розподіл має більш високий пріоритет.

Ви повинні написати свій код, щоб висловити свої наміри. Якщо продуктивність ваша турбота, не хвилюйтеся, оптимізатор добре справляється з такими мікро-оптимізаціями.

62
21 мая '12 в 10:59 2012-05-21 10:59 відповідь дан Luchian Grigore 21 травня '12 о 10:59 2012-05-21 10:59

Просто використовуйте divide ( / ), припускаючи, що він більш ясний. Відповідно буде оптимізований компілятор.

57
21 мая '12 в 10:56 2012-05-21 10:56 відповідь дан justin 21 травня '12 о 10:56 2012-05-21 10:56

Я згоден з іншими відповідями, що ви повинні схвалити x / 2 , тому що його намір більш чітке, і компілятор повинен оптимізувати його для вас.

Однак іншою причиною перевагу x / 2 over x >> 1 є те, що поведінка >> залежить від реалізації, якщо x є підписаним int і є негативним.

З розділу 6.5.7, куля 5 стандарту ISO C99:

Результатом E1 >> E2 є E1 зміщення по правому краю E2 . Якщо E1 має беззнаковий тип або якщо E1 має підписаний тип і позитивне значення, значення результату є невід'ємною частиною фактора E1 / 2 E2 . Якщо E1 має підписаний тип і негативне значення, результуюче значення визначається реалізацією.

38
21 мая '12 в 11:02 2012-05-21 11:02 відповідь дан jamesdlin 21 травня '12 о 11:02 2012-05-21 11:02

x / 2 більш ясний, а x >> 1 не набагато швидше (згідно мікро-бенчмарку, приблизно на 30% швидше для Java JVM). Як відзначали інші, для негативних чисел округлення трохи відрізняється, тому ви повинні враховувати це, коли хочете обробляти негативні числа. Деякі компілятори можуть автоматично перетворювати x / 2 в x >> 1 , якщо вони знають, що число не може бути негативним (навіть я не міг перевірити це).

Навіть x / 2 може не використовувати інструкцію з повільним поділом CPU, тому що деякі ярлики можливі , але вона все ще повільніше, ніж x >> 1 .

(Це питання на C / С ++, інші мови програмування мають більше операторів. Для Java також є зрушення без знака, x >>> 1 , який знову відрізняється. Він дозволяє правильно розрахувати середнє (середнє) значення два значення, так що (a + b) >>> 1 поверне середнє значення навіть для дуже великих значень a і b . Це потрібно, наприклад, для двійкового пошуку, якщо індекси масиву можуть бути дуже великими. Було помилка в багатьох версіях бінарного пошуку , тому що вони використовували (a + b) / 2 для обчислення середнього значення.Це не працює правильно. Правильне реш ення полягає у використанні (a + b) >>> 1 .)

32
21 мая '12 в 10:57 2012-05-21 10:57 відповідь дан Thomas Mueller 21 травня '12 о 10:57 2012-05-21 10:57

Кнут сказав:

Передчасна оптимізація - це корінь усього зла.

Тому я пропоную використовувати x /= 2;

Таким чином, код легко зрозуміти, і я думаю, що оптимізація цієї операції в цій формі не означає великої різниці для процесора.

22
23 мая '12 в 2:58 2012-05-23 02:58 відповідь дан Ivan Californias 23 травня '12 о 2:58 2012-05-23 2:58

Подивіться на висновок компілятора, який допоможе вам вирішити. Я перевірив цей тест на x86-64 за допомогою gcc (GCC) 4.2.1 20070719 [FreeBSD]

Також см. Компілятор виводить онлайн в godbolt .

Ви бачите, що в обох випадках компілятор використовує інструкцію sarl (арифметичний зрушення вправо), тому він розпізнає схожість між цими двома виразами. Якщо ви використовуєте поділ, компілятор також повинен налаштувати негативні числа. Для цього він зрушує біт знака до молодшого біта і додає його до результату. Це усуває проблему "один за іншим" при зміщенні негативних чисел в порівнянні з тим, що буде робити поділ.
Так як випадок поділу має 2 зміни, тоді як явний випадок зсуву тільки один, ми тепер можемо пояснити деякі відмінності в продуктивності, виміряні іншими відповідями тут.

Код C зі складанням:

Для поділу ваш вхід буде

 int div2signed(int a) { return a / 2; } 

і це компілюється в

  movl %edi, %eax shrl $31, %eax addl %edi, %eax sarl %eax ret 

аналогічно для зсуву

 int shr2signed(int a) { return a >> 1; } 

з виходом:

  sarl %edi movl %edi, %eax ret 
17
27 мая '12 в 3:32 2012-05-27 03:32 відповідь дан Michael Donohue 27 травня '12 о 3:32 2012-05-27 3:32

Просто доданий примітка -

x * = 0.5 часто буде швидше в деяких мовах на основі VM, зокрема ActionScript, так як змінна не повинна бути перевірена для поділу на 0.

15
21 мая '12 в 21:46 2012-05-21 21:46 відповідь дан ansiart 21 травня '12 о 21:46 2012-05-21 21:46

Використовуйте x = x / 2; АБО x /= 2; . Можливо, що в майбутньому новий програміст буде працювати над цим. Тому йому буде легше дізнатися, що відбувається в рядку коду. Будь-хто може не знати про таку оптимізації.

13
22 мая '12 в 8:58 2012-05-22 08:58 відповідь дан Imdad 22 травня '12 о 8:58 2012-05-22 8:58

Я говорю для цілей змагань з програмування. Як правило, вони мають дуже великі входи, де поділ на 2 відбувається багато раз, і відомо, що введення позитивний або негативний.

x → 1 буде краще, ніж x / 2. Я перевірив на ideone.com, запустивши програму, де сталося понад 10 ^ 10 поділок на 2 операції. x / 2 зайняло майже 5,5 с, тоді як x → 1 зайняло близько 2,6 с для тієї ж програми.

12
21 мая '12 в 21:39 2012-05-21 21:39 відповідь дан Shashwat Kumar 21 травня '12 о 21:39 2012-05-21 21:39

Я б сказав, що є кілька речей, які слід враховувати.

  • Bitshift повинен бути швидше, оскільки ніякі спеціальні обчислення насправді необхідно було зрушити біт, проте, як зазначено, є потенційні проблеми з негативним числом. Якщо у вас є позитивні числа, і шукають швидкість, тоді я б порекомендував Bitshift.

  • Оператор поділу дуже простий для читання людьми. Тому, якщо ви шукаєте читаність коду, ви можете використовувати це. Замітка що поле оптимізації компілятора пройшло довгий шлях, тому спростити код читати і розуміти - це хороша практика.

  • Залежно від основного устаткування, операції можуть мати різні швидкості. Amdal закон повинен зробити звичайний випадок швидко. Таким чином, у вас може бути обладнання, яке може виконувати різні операції швидше за інших. Наприклад, множачи на 0.5 може бути швидше, ніж розподіл на 2. (Звичайно, вам може знадобитися взяти слово множення, якщо ви хочете застосувати цілочисельне ділення).

Якщо ви після чистої продуктивності, я б рекомендував створити кілька тестів, які могли б виконувати операції мільйони разів. Спробуйте виконати кілька разів (розмір вибірки), щоб визначити, який з них статистично найкраще підходить для вашої OS / Hardware / Compiler / Code.

12
21 мая '12 в 23:21 2012-05-21 23:21 відповідь дан James Oravec 21 травня '12 о 23:21 2012-05-21 23:21

Що стосується процесора, операції біт-зсуву швидше операцій ділення. Однак компілятор знає про це і буде оптимізований відповідним чином в тій мірі, в якій це можливо, так що ви можете кодувати таким чином, щоб максимально зручно і спокійно, знаючи, що ваш код працює ефективно. Але пам'ятайте, що unsigned int може (в деяких випадках) оптимізуватися краще, ніж int по раніше наведених причин. Якщо вам не потрібна підписана арифметика, тоді не включайте знаковий біт.

12
22 мая '12 в 4:17 2012-05-22 04:17 відповідь дан tylerl 22 травня '12 в 4:17 2012-05-22 4:17

x = x / 2; це відповідний код для використання. але операція залежить від вашої власної програми того, як ви хочете зробити висновок.

11
21 мая '12 в 15:07 2012-05-21 15:07 відповідь дан Gooner 21 травня '12 о 15:07 2012-05-21 15:07

Зробіть ваші наміри яснішими ... наприклад, якщо ви хочете розділити, використовуйте x / 2, і нехай компілятор оптимізує його для перемикання оператора (або чогось ще).

Сьогодні процесори не дозволять цим оптимізації впливати на продуктивність ваших програм.

11
22 мая '12 в 11:29 2012-05-22 11:29 відповідь дан Atul Kumar 22 травня '12 о 11:29 2012-05-22 11:29

Відповідь на це буде залежати від середовища, в якій ви працюєте.

  • Якщо ви працюєте з 8-розрядних мікроконтролерів або чим-небудь без апаратної підтримки для множення, очікується, що зміщення бітів буде звичайним явищем, і хоча компілятор майже напевно перетворить x /= 2 в x >>= 1 , наявність розподілу символ буде піднімати більше брів в цьому середовищі, ніж використовувати зрушення, щоб зробити розподіл.
  • Якщо ви працюєте в критичною для продуктивності середовищі або розділі коду, або ваш код може бути скомпільований з оптимізацією компілятора, x >>= 1 з коментарем, що пояснює його аргументацію, ймовірно, краще за все для ясності мети.
  • Якщо ви не перебуваєте в одній із вищевказаних умов, зробіть свій код більш зручним для читання, просто використовуючи x /= 2 . Краще зберегти наступного програміста, який, трапляється, дивиться на ваш код 10-секундного подвійної дії на вашу операцію перемикання, ніж без необхідності доводити, що ви знали, що зміна була більш ефективною без оптимізації компілятора.

Всі вони припускають цілі числа без знака. Простий зсув, ймовірно, не той, який ви хочете для підписання. Крім того, DanielH дуже добре розбирається у використанні x *= 0.5 для певних мов, таких як ActionScript.

10
23 мая '12 в 0:11 2012-05-23 00:11 відповідь дан gkimsey 23 травня '12 в 0:11 2012-05-23 00:11

mod 2, test for = 1. dunno синтаксис в c. але це може бути найшвидшим.

8
21 мая '12 в 23:30 2012-05-21 23:30 відповідь дан circusdei 21 травня '12 о 23:30 2012-05-21 23:30

загальний правий зсув ділиться:

 q = i >> n; is the same as: q = i / 2**n; 

це іноді використовується для прискорення програм за рахунок ясності. Я не думаю, що ти повинен це зробити. Компілятор досить розумний, щоб автоматично виконувати прискорення. Це означає, що перенесення зсуву не дає вам нічого за рахунок ясності.

Погляньте на цю сторінку з Практичного програмування на C ++.

7
22 мая '12 в 13:41 2012-05-22 13:41 відповідь дан Mouna Cheikhna 22 травня '12 о 13:41 2012-05-22 13:41

Очевидно, що якщо ви пишете свій код для наступного хлопця, який його читає, йдіть за ясність "x / 2".

Однак, якщо швидкість - ваша мета, спробуйте в обох напрямках і часу результати. Кілька місяців тому я працював над растрової схемою згортки, яка включала в себе перехід через масив цілих чисел і розподіл кожного елемента 2. Я зробив все можливе, щоб оптимізувати його, включаючи старий трюк підстановки "x → 1" для "x / 2".

Коли я дійсно приурочив обидва способи, я з подивом виявив, що x / 2 швидше, ніж x → 1

Це використовувало Microsoft VS2008 С ++ з включеною оптимізацією за замовчуванням.

7
08 июня '12 в 14:34 2012-06-08 14:34 відповідь дан Chris Bennet 08 червня '12 в 14:34 2012-06-08 14:34

З точки зору продуктивності. Операції зміни процесора значно швидше, ніж деактивувати op-коди. Таким чином, поділ на два або множення на 2 і т.д. Всі вигоди від операцій зміни.

Що стосується зовнішнього вигляду. Як інженери, коли ми стали настільки прив'язані до косметики, що навіть прекрасні дами не використовують! :)

4
22 мая '12 в 20:25 2012-05-22 20:25 відповідь дан Farjad 22 травня '12 о 20:25 2012-05-22 20:25

X / Y - правильний оператор ... і "→". Якщо ми хочемо, щоб два розділили ціле число, ми можемо використовувати (/) оператор дивідендів. оператор зсуву використовується для зсуву біт.

х = х / 2; х / = 2; ми можемо так використовувати.

3
25 мая '12 в 8:51 2012-05-25 08:51 відповідь дан chocolate boy 25 травня '12 в 8:51 2012-05-25 8:51

У той час як x → 1 швидше, ніж x / 2, правильне використання → при роботі з негативними значеннями трохи складніше. Для цього потрібно щось схоже на наступне:

 // Extension Method public static class Global { public static int ShiftDivBy2(this int x) { return (x < 0 ? x + 1 : x) >> 1; } } 
0
21 дек. відповідь дан Darin 21 дек. 2016-12-21 09:41 '16 в 9:41 2016-12-21 9:41

Інші питання по мітках або Задайте питання