Ответ 1

Этот ответ о том, какой идеал в asm; что мы хотели бы убедить компилятор испустить для нас. (Я не предлагаю на самом деле использовать inline asm, за исключением точки сравнения при выводе компилятора для сравнения. https://gcc.gnu.org/wiki/DontUseInlineAsm).

Мне удалось получить довольно хороший выход asm из чистого C для ceil_div_andmask, см. ниже. (Это хуже, чем CMOV на Broadwell/Skylake, но, вероятно, хорошо на Haswell. версия user23/chux выглядит даже лучше для обоих случаев.) Это в основном просто стоит упомянуть как один из немногих случаев, когда я получил компилятор для извлечения asm, который я хотел.

Похоже, что идея Криса Додда о return ((p-1) >> lg(q)) + 1 с обработкой специального случая для d = 0 является одним из лучших вариантов. То есть оптимальная реализация его в asm трудно превзойти с оптимальной реализацией чего-либо еще. У Chux (p >> lg(q)) + (bool)(p & (q-1)) также есть преимущества (например, более низкая латентность от результата p- > ) и более CSE, когда один и тот же q используется для нескольких разделов, Ниже приведен анализ задержки/пропускной способности того, что gcc делает с ним.

Если один и тот же e = lg(q) повторно используется для нескольких дивидендов или один и тот же дивиденд используется повторно для нескольких делителей, различные реализации могут CSE больше выражения. Они также могут эффективно векторизовать с помощью AVX2.

Филиалы дешевы и очень эффективны, если они прогнозируют очень хорошо, поэтому разветвление на d==0 будет лучше, если оно почти никогда не будет принято. Если d==0 не является редкими, нераспространяющийся asm будет работать лучше в среднем. В идеале мы можем написать что-то в C, которое позволит gcc сделать правильный выбор во время оптимизации на основе профиля и скомпилировать его с хорошим asm для любого случая.

Так как лучшие безветровые реализации asm не добавляют много латентности против разветвленной реализации, веткистая, вероятно, способ пойти, если ветка не будет идти одинаково, может быть, в 99% случаев. Вероятно, это возможно для ветвления на p==0, но, вероятно, менее вероятно для ветвления на p & (q-1).

Трудно направить gcc5.4 на испускание чего-либо оптимального. Это моя работа над Godbolt).

Я думаю, что оптимальные последовательности для Skylake для этого алгоритма заключаются в следующем. (Представлены как автономные функции для AMD64 SysV ABI, но говорят о пропускной способности/задержке в предположении, что компилятор будет выпустить что-то подобное в виде петли без привязки RET).

Ветвь на переносе от вычисления d-1 для обнаружения d == 0 вместо отдельного теста и ветки. Уменьшает счетчик uop красиво, esp на семействе SnB, где JC может сжимать макрос с SUB.

ceil_div_pjc_branch:
 xor    eax,eax          ; can take this uop off the fast path by adding a separate xor-and-return block, but in reality we want to inline something like this.
 sub    rdi, 1
 jc    .d_was_zero       ; fuses with the sub on SnB-family
 tzcnt  rax, rsi         ; tzcnt rsi,rsi also avoids any false-dep problems, but this illustrates that the q input can be read-only.
 shrx   rax, rdi, rax
 inc    rax
.d_was_zero:
 ret

• Fused-domain uops: 5 (не считая ret), а один из них - xor-zero (без исполнительного блока)
• Задержка HSW/SKL с успешным предсказанием ветвления:
  • (d == 0): нет зависимости от данных d или q, разрывает цепочку dep. (управляющая зависимость от d для обнаружения ошибочных прогнозов и выхода из ветки).
  • (d!= 0): q- > result: tzcnt + shrx + inc = 5c
  • (d!= 0): d- > результат: sub + shrx + inc = 3c
• Пропускная способность: возможно, просто узкое место по пропускной способности uop

Я пробовал, но не смог получить gcc для перехода на CF из вычитания, но он всегда хочет провести отдельное сравнение. Я знаю, что gcc можно уговорить на ветвление на CF после вычитания двух переменных, но, возможно, это не удается, если вы являетесь константой времени компиляции. (IIRC, это обычно компилируется в CF-тест с неподписанными vars: foo -= bar; if(foo>bar) carry_detected = 1;)

Без ветвления с ADC/SBB для обработки события d==0. Zero-handling добавляет только одну инструкцию к критическому пути (по сравнению с версией без специальной обработки для d == 0), но также преобразует еще одну из INC в sbb rax, -1, чтобы сделать CF отмененным -= -1. Использование CMOV дешевле на pre-Broadwell, но требует дополнительных инструкций по настройке.

ceil_div_pjc_asm_adc:
 tzcnt  rsi, rsi
 sub    rdi, 1
 adc    rdi, 0          ; d? d-1 : d.  Sets CF=CF
 shrx   rax, rdi, rsi
 sbb    rax, -1         ; result++ if d was non-zero
 ret    

• Fused-domain uops: 5 (не считая ret) на SKL. 7 по HSW
• Задержка SKL:
  • q- > результат: tzcnt + shrx + sbb = 5c
  • d- > result: sub + adc + shrx (здесь начинается деление на q) + sbb = 4c
• Пропускная способность: TZCNT работает на p1. SBB, ADC и SHRX работают только на p06. Таким образом, я думаю, что мы сглаживаем 3 раза за p06 за итерацию, делая этот запуск в лучшем случае одной итерацией за 1.5c.

Если q и d станут готовыми одновременно, обратите внимание, что эта версия может запускать SUB/ADC параллельно с задержкой 3c для TZCNT. Если оба они поступают из одной и той же кешированной кэш-линии, это, безусловно, возможно. В любом случае преимущество в определении q как можно позже в цепочке зависимостей результатов d- > является преимуществом.

Получение этого из С представляется маловероятным с помощью gcc5.4. Существует встроенная функция add-with-carry, но gcc создает полный беспорядок. Он не использует непосредственные операнды для АЦП или SBB и сохраняет перенос в целочисленную регистрацию между каждой операцией. gcc7, clang3.9 и icc17 делают из этого ужасный код.

#include <x86intrin.h>
// compiles to completely horrible code, putting the flags into integer regs between ops.
T ceil_div_adc(T d, T q) {
  T e = lg(q);
  unsigned long long dm1;  // unsigned __int64
  unsigned char CF = _addcarry_u64(0, d, -1, &dm1);
  CF = _addcarry_u64(CF, 0, dm1, &dm1);
  T shifted = dm1 >> e;
  _subborrow_u64(CF, shifted, -1, &dm1);
  return dm1;
}
    # gcc5.4 -O3 -march=haswell
    mov     rax, -1
    tzcnt   rsi, rsi
    add     rdi, rax
    setc    cl
    xor     edx, edx
    add     cl, -1
    adc     rdi, rdx
    setc    dl
    shrx    rdi, rdi, rsi
    add     dl, -1
    sbb     rax, rdi
    ret

CMOV, чтобы исправить весь результат: худшая латентность от результата q- > , так как она раньше использовалась в цепочке отрезка результата d- > .

ceil_div_pjc_asm_cmov:
 tzcnt  rsi, rsi
 sub    rdi, 1
 shrx   rax, rdi, rsi
 lea    rax, [rax+1]     ; inc preserving flags
 cmovc  rax, zeroed_register
 ret    

• Fused-domain uops: 5 (не считая ret) на SKL. 6 по HSW
• Задержка SKL:
  • q- > результат: tzcnt + shrx + lea + cmov = 6c (хуже, чем ADC/SBB на 1c)
  • d- > результат: sub + shrx (здесь начинается от q) + lea + cmov = 4c
• Пропускная способность: TZCNT работает на p1. LEA - p15. CMOV и SHRX - p06. SUB - p0156. Теоретически только узкое место в пропускной способности uop с плавным доменом, поэтому одна итерация на 1.25c. При наличии большого количества независимых операций конфликты ресурсов из SUB или LEA, кража p1 или p06, не должны быть проблемой пропускной способности, поскольку при 1 инерции на 1.25c ни один порт не насыщен uops, который может работать только на этом порту.

CMOV, чтобы получить операнд для SUB: я надеялся, что смогу найти способ создания операнда для более поздней инструкции, которая при необходимости создавала бы нуль без зависимости ввода от q, e, или результат SHRX. Это помогло бы, если d готов до q или в то же время.

Это не достигает этой цели и нуждается в дополнительном 7-байтовом mov rdx,-1 в цикле.

ceil_div_pjc_asm_cmov:
 tzcnt  rsi, rsi
 mov    rdx, -1
 sub    rdi, 1
 shrx   rax, rdi, rsi
 cmovnc rdx, rax
 sub    rax, rdx       ; res += d ? 1 : -res
 ret    

версия с низкой задержкой для процессоров с предварительным BDW с дорогостоящим CMOV, используя SETCC для создания маски для AND.

ceil_div_pjc_asm_setcc:
 xor    edx, edx        ; needed every iteration

 tzcnt  rsi, rsi
 sub    rdi, 1

 setc   dl              ; d!=0 ?  0 : 1
 dec    rdx             ; d!=0 ? -1 : 0   // AND-mask

 shrx   rax, rdi, rsi
 inc    rax
 and    rax, rdx        ; zero the bogus result if d was initially 0
 ret    

Тем не менее 4c задержка от результата d- > (и 6 из результата q- > ), поскольку SETC/DEC происходит параллельно с SHRX/INC. Total uop count: 8. Большинство из этих insns могут работать на любом порту, поэтому он должен быть 1 итера за 2 такта.

Конечно, для pre-HSW вам также необходимо заменить SHRX.

Мы можем получить gcc5.4, чтобы испустить что-то почти хорошее: (по-прежнему использует отдельный TEST вместо установки маски на основе sub rdi, 1, но в остальном те же инструкции, что и выше). Смотрите в Godbolt.

T ceil_div_andmask(T p, T q) {
    T mask = -(T)(p!=0);  // TEST+SETCC+NEG
    T e = lg(q);
    T nonzero_result = ((p-1) >> e) + 1;
    return nonzero_result & mask;
}

Когда компилятор знает, что p отличен от нуля, он использует преимущество и делает хороший код:

// http://stackoverflow.com/questions/40447195/can-i-hint-the-optimizer-by-giving-the-range-of-an-integer
#if defined(__GNUC__) && !defined(__INTEL_COMPILER)
#define assume(x) do{if(!(x)) __builtin_unreachable();}while(0)
#else
#define assume(x) (void)(x) // still evaluate it once, for side effects in case anyone is insane enough to put any inside an assume()
#endif

T ceil_div_andmask_nonzerop(T p, T q) {
  assume(p!=0);
  return ceil_div_andmask(p, q);
}
    # gcc5.4 -O3 -march=haswell
    xor     eax, eax             # gcc7 does tzcnt in-place instead of wasting an insn on this
    sub     rdi, 1
    tzcnt   rax, rsi
    shrx    rax, rdi, rax
    add     rax, 1
    ret

Chux/user23_variant

только 3c латентность от результата p- > , а константа q может много CSE.

T divide_A_chux(T p, T q) {
  bool round_up = p & (q-1);  // compiles differently from user23_variant with clang: AND instead of 
  return (p >> lg(q)) + round_up;
}

    xor     eax, eax           # in-place tzcnt would save this
    xor     edx, edx           # target for setcc
    tzcnt   rax, rsi
    sub     rsi, 1
    test    rsi, rdi
    shrx    rdi, rdi, rax
    setne   dl
    lea     rax, [rdx+rdi]
    ret

Выполнение SETCC перед TZCNT позволит использовать TZCNT на месте, сохраняя xor eax,eax. Я не смотрел, как это происходит в цикле.

• Fused-domain uops: 8 (не считая ret) на HSW/SKL
• Задержка HSW/SKL:
  • q- > result: (tzcnt + shrx (p) | sub + test (p) + setne) + lea (или add) = 5c
  • d- > результат: test (здесь начинается от q) + setne + lea = 3c. (цепочка shrx- > lea короче и, следовательно, не критический путь)
• Пропускная способность: возможно, только узкое место на интерфейсе, на один раз за 2c. Сохранение xor eax,eax должно ускорить это до 1 на 1.75c (но, конечно, любые накладные расходы цикла будут частью узкого места, потому что узкие места в интерфейсе подобны).

Ответ 2

uint64_t exponent = lg(q);
uint64_t mask = q - 1;
//     v divide
return (p >> exponent) + (((p & mask) + mask) >> exponent)
//                       ^ round up

Отдельное вычисление части "round up" позволяет избежать проблем с переполнением (p+q-1) >> lg(q). В зависимости от того, насколько интеллектуальным является ваш компилятор, может быть возможно выразить часть "round up" как ((p & mask) != 0) без разветвления.

Ответ 3

Эффективный способ деления на 2 для беззнакового целого числа в C является правым сдвигом сдвига вправо, разделяемым на два (округление вниз), поэтому смещение справа на n делит на 2 ⁿ (округление).

Теперь вы хотите округлить, а не вниз, что вы можете сделать, сначала добавив 2 ⁿ -1 или эквивалентно вычитая один перед сдвигом и добавив один после (кроме 0). Это работает примерно так:

unsigned ceil_div(unsigned d, unsigned e) {
    /* compute ceil(d/2**e) */
    return d ? ((d-1) >> e) + 1 : 0;
}

Условие можно удалить, используя логическое значение d для сложения и вычитания единицы:

unsigned ceil_div(unsigned d, unsigned e) {
    /* compute ceil(d/2**e) */
    return ((d - !!d) >> e) + !!d;
}

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

static inline unsigned ceil_div(const unsigned d, const unsigned e){...

Ответ 4

Эффективное разделение неподписанного значения на степень двух, округление

[Повторно написать], учитывая OP разъяснение относительно мощности-2.

Завершающая или потолочная часть проста, когда переполнение не вызывает беспокойства. Просто добавьте q-1, затем сдвиньте.

В противном случае, поскольку возможность округления зависит от всех бит p меньше, чем q, обнаружение этих бит необходимо прежде, чем они будут сдвинуты.

uint64_t divide_A(uint64_t p, uint64_t q) {
  bool round_up = p & (q-1);
  return (p >> lg64(q)) + round_up;
} 

Это предполагает, что код имеет эффективную функцию lg64(uint64_t x), которая возвращает журнал базового 2 x, если x является степенью двух.

Ответ 5

Мой старый ответ не сработал, если p был чем-то большим, чем силой двух (крики). Итак, мое новое решение, использующее функции __builtin_ctzll() и __builtin_ffsll() ⁰ доступные в gcc (который в качестве бонуса предоставляет быстрый логарифм, который вы упомянули!):

uint64_t divide(uint64_t p,uint64_t q) {
    int lp=__builtin_ffsll(p);
    int lq=__builtin_ctzll(q);
    return (p>>lq)+(lp<(lq+1)&&lp);
}

Обратите внимание, что это предполагает, что a long long - 64 бит. Это должно быть изменено немного иначе.

Идея здесь в том, что если нам нужно переполнение тогда и только тогда, когда p имеет меньше конечных нулей, чем q. Обратите внимание, что для мощности двух число конечных нулей равно логарифму, поэтому мы также можем использовать этот встроенный для журнала.

Часть &&lp предназначена только для случая угла, где p равно нулю: в противном случае здесь будет выводиться 1.

⁰ Нельзя использовать __builtin_ctzll() для обоих, потому что это undefined, если p==0.

Ответ 6

Если дивиденд/делитель может быть гарантированно не превышать 63 (или 31) бита, вы можете использовать следующую версию, указанную в вопросе. Обратите внимание, как p + q может переполняться, если они используют все 64 бит. Это было бы хорошо, если команда SHR сдвигалась в флагом переноса, но AFAIK это не делает.

uint64_t divide(uint64_t p, uint64_t q) {
  return (p + q - 1) >> lg(q);
}

Если эти ограничения не могут быть гарантированы, вы можете просто сделать метод пола, а затем добавить 1, если он будет округлен. Это можно определить, проверяя, находятся ли какие-либо биты в дивиденде в пределах диапазона делителя. Примечание: p & -p извлекает младший бит набора на машинах с дополнением 2s или инструкцию BLSI

uint64_t divide(uint64_t p, uint64_t q) {
  return (p >> lg(q)) + ( (p & -p ) < q );
}

Какой clang компилируется в:

    bsrq    %rax, %rsi
    shrxq   %rax, %rdi, %rax
    blsiq   %rdi, %rcx
    cmpq    %rsi, %rcx
    adcq    $0, %rax
    retq

Это немного словесно и использует некоторые новые инструкции, поэтому, возможно, есть способ использовать флаг переноса в исходной версии. Посмотрим: RCR инструкция, но похоже, что было бы хуже... возможно SHRD... Это было бы что-то вроде этого (невозможно проверить на данный момент)

    xor     edx, edx     ;edx = 0 (will store the carry flag)
    bsr     rcx, rsi     ;rcx = lg(q) ... could be moved anywhere before shrd
    lea     rax, [rsi-1] ;rax = q-1 (adding p could carry)
    add     rax, rdi     ;rax += p  (handle carry)
    setc    dl           ;rdx = carry flag ... or xor rdx and setc
    shrd    rax, rdx, cl ;rax = rdx:rax >> cl
    ret

Еще одна инструкция, но должна быть совместима со старыми процессорами (если она работает... Я всегда получаю исходный/целевой обмен, не стесняйтесь редактировать)

Приложение:

Я реализовал функцию lg(), которую я сказал, был доступен следующим образом:

inline uint64_t lg(uint64_t x) {
  return 63U - (uint64_t)__builtin_clzl(x);
}

inline uint32_t lg32(uint32_t x) {
  return 31U - (uint32_t)__builtin_clz(x);
}

Функции быстрого журнала не полностью оптимизируются для bsr на clang и ICC, но вы можете это сделать:

#if defined(__x86_64__) && (defined(__clang__) || defined(__INTEL_COMPILER))
static inline uint64_t lg(uint64_t x){
  inline uint64_t ret;
  //other compilers may want bsrq here
  __asm__("bsr  %0, %1":"=r"(ret):"r"(x));
  return ret;
}
#endif

#if defined(__i386__) && (defined(__clang__) || defined(__INTEL_COMPILER))    static inline uint32_t lg32(uint32_t x){
  inline uint32_t ret;
  __asm__("bsr  %0, %1":"=r"(ret):"r"(x));
  return ret;
}
#endif

Ответ 7

К этой проблеме уже приложено много человеческих мозговых возможностей с несколькими вариантами отличных ответов в C вместе с ответом Питера Кордеса, который охватывает все, на что можно надеяться в asm, с заметками о попытке сопоставить его вернуться к C.

Таким образом, пока люди пишут в банке, я подумал, что нужно сказать о какой-то грубой вычислительной мощности! С этой целью я использовал Stanford STOKE superoptimizer, чтобы попытаться найти хорошие решения для 32-разрядных и 64-разрядных версий этой проблемы.

Обычно, супероптимизатор обычно является чем-то вроде поиска грубой силы через все возможные последовательности команд, пока вы не найдете лучший по какой-либо метрике. Конечно, с что-то вроде 1000 инструкций, которое быстро выйдет из-под контроля для нескольких команд ¹. STOKE, на руке, использует ориентированный рандомизированный подход: он случайным образом превращает мутации в существующую кандидатную программу, оценивая на каждом шаге функцию стоимости, которая выполняет как эффективность, так и правильность. В любом случае однострочный лайнер - много бумаг, если это вызвало ваше любопытство.

Итак, через несколько минут STOKE нашел несколько довольно интересных решений. Он нашел почти все идеи высокого уровня в существующих решениях, а также несколько уникальных. Например, для 32-битной функции STOKE нашел эту версию:

neg rsi                         
dec rdi                         
pext rax, rsi, rdi
inc eax
ret

Он не использует никаких указаний о переходе/переходе на нуль или сдвиге вообще. В значительной степени он использует neg esi, чтобы превратить делитель в маску с 1s в высоких битах, а затем pext эффективно выполняет сдвиг с использованием этой маски. Вне этого трюка он использует тот же трюк, что и пользователь QuestionC: декремент p, shift, increment p - но он работает даже для нулевого дивиденда, потому что он использует 64-битные регистры, чтобы отличить нулевой регистр от MSB-набора больших p case.

Я добавил версию C этого алгоритма к эталону и добавил его к результатам. Он конкурирует с другими хорошими алгоритмами, привязывая их сначала к "переменным Q" . Он выполняет векторизация, но не так же хорошо, как и другие 32-битные алгоритмы, поскольку для этого требуется 64-битная математика, и поэтому векторы могут обрабатывать только половину количества элементов одновременно.

Еще лучше, в 32-битном случае он придумал множество решений, которые используют тот факт, что некоторые интуитивные решения, которые терпят неудачу для краевых случаев, "просто работают", если вы используете 64-битные операционные системы для части из этого. Например:

tzcntl ebp, esi      
dec esi             
add rdi, rsi        
sarx rax, rdi, rbp
ret

Это эквивалент предложения return (p + q - 1) >> lg(q), упомянутого в вопросе. Это не работает вообще, так как для больших p + q он переполняется, но для 32-разрядных p и q это решение отлично работает, занимая важные части в 64-битной версии. Преобразуйте это обратно в C с помощью некоторых приведений, и на самом деле выясняется, что использование lea сделает добавление в одной команде ¹

stoke_32(unsigned int, unsigned int):
        tzcnt   edx, esi
        mov     edi, edi          ; goes away when inlining
        mov     esi, esi          ; goes away when inlining
        lea     rax, [rsi-1+rdi]
        shrx    rax, rax, rdx
        ret

Таким образом, это решение с тремя командами, когда оно встроено в нечто, которое уже имеет значения, равные нулю, в rdi и rsi. Для определения автономной функции требуются инструкции mov для нулевого расширения, поскольку как работает ABI SysV x64.

Для 64-битной функции она не придумала ничего, что сдуло бы существующие решения, но придумал некоторые аккуратные вещи, например:

  tzcnt  r13, rsi      
  tzcnt  rcx, rdi      
  shrx   rax, rdi, r13 
  cmp    r13b, cl        
  adc    rax, 0        
  ret

Этот парень учитывает конечные нули обоих аргументов, а затем добавляет 1 к результату, если q имеет меньше конечных нулей, чем p, так как это нужно, чтобы округлить. Умно!

В целом, он понял идею, что вам нужно shl tzcnt очень быстро (как и большинство людей), а затем придумал массу других решений проблемы настройки результата для учета округления. Ему даже удалось использовать blsi и bzhi в нескольких решениях. Здесь было предложено 5-командное решение:

tzcnt r13, rsi                  
shrx  rax, rdi, r13             
imul  rsi, rax                   
cmp   rsi, rdi                    
adc   rax, 0                    
ret 

Это в основном подход "умножить и проверить" - возьмите усеченный res = p \ q, умножьте его обратно и, если он отличается от p, добавьте один: return res * q == p ? ret : ret + 1. Круто. Однако не лучше, чем решения Peter. У STOKE, по-видимому, есть некоторые недостатки в расчете латентности - он считает, что у вышеупомянутого есть латентность 5 - но это больше похоже на 8 или 9 в зависимости от архитектуры. Поэтому он иногда сужается в решениях, основанных на его ошибочном вычислении латентности.

¹ Интересно, хотя этот подход с грубой силой достигает своей выполнимости около 5-6 команд: если вы предполагаете, что можете урезать количество команд, чтобы сказать 300, исключив инструкции SIMD и x87, тогда вам понадобится ~ 28 дней, чтобы попробовать все 300 ^ 5 5 последовательностей команд со скоростью 1 000 000 кандидатов в секунду. Вы могли бы уменьшить это в 1000 раз с различными оптимизациями, что означает менее часа для 5-командных последовательностей и, возможно, неделю для 6-инструкций. Как это бывает, большинство лучших решений этой проблемы попадают в это окно с инструкциями 5-6...

² Это будет медленным lea, поэтому последовательность, найденная STOKE, по-прежнему оптимальна для того, для чего я оптимизирован, что было латентностью.

Ответ 8

Вы можете сделать это так, сравнивая разделение n / d с делением на (n-1) / d.

#include <stdio.h>

int main(void) {
    unsigned n;
    unsigned d;
    unsigned q1, q2;
    double actual;

    for(n = 1; n < 6; n++) {
        for(d = 1; d < 6; d++) {
            actual = (double)n / d;
            q1 = n / d;
            if(n) {
                q2 = (n - 1) / d;
                if(q1 == q2) {
                    q1++;
                }
            }
            printf("%u / %u = %u (%f)\n", n, d, q1, actual);
        }
    }

    return 0;
}

Выход программы:

1 / 1 = 1 (1.000000)
1 / 2 = 1 (0.500000)
1 / 3 = 1 (0.333333)
1 / 4 = 1 (0.250000)
1 / 5 = 1 (0.200000)
2 / 1 = 2 (2.000000)
2 / 2 = 1 (1.000000)
2 / 3 = 1 (0.666667)
2 / 4 = 1 (0.500000)
2 / 5 = 1 (0.400000)
3 / 1 = 3 (3.000000)
3 / 2 = 2 (1.500000)
3 / 3 = 1 (1.000000)
3 / 4 = 1 (0.750000)
3 / 5 = 1 (0.600000)
4 / 1 = 4 (4.000000)
4 / 2 = 2 (2.000000)
4 / 3 = 2 (1.333333)
4 / 4 = 1 (1.000000)
4 / 5 = 1 (0.800000)
5 / 1 = 5 (5.000000)
5 / 2 = 3 (2.500000)
5 / 3 = 2 (1.666667)
5 / 4 = 2 (1.250000)
5 / 5 = 1 (1.000000)

Обновление

Я опубликовал ранний ответ на исходный вопрос, который работает, но не учитывал эффективность алгоритма или что делитель всегда имеет силу 2. Выполнение двух делений было бесполезно дорого.

Я использую 32-разрядный компилятор MSVC в 64-битной системе, поэтому нет никаких шансов, что я смогу обеспечить наилучшее решение для требуемой цели. Но это интересный вопрос, поэтому я попытался найти, что лучшее решение обнаружит бит 2 ** n делителя. Использование функции библиотеки log2 работало, но было настолько медленным. Выполнение моей собственной смены было намного лучше, но все же мой лучший C-решение -

unsigned roundup(unsigned p, unsigned q)
{
    return p / q + ((p & (q-1)) != 0);
}

Мое встроенное 32-битное ассемблерное решение выполняется быстрее, но, конечно, это не ответит на вопрос. Я краду несколько циклов, предположив, что eax возвращается как значение функции.

unsigned roundup(unsigned p, unsigned q)
{
    __asm {
        mov eax,p
        mov edx,q
        bsr ecx,edx     ; cl = bit number of q
        dec edx         ; q-1
        and edx,eax     ; p & (q-1)
        shr eax,cl      ; divide p by q, a power of 2
        sub edx,1       ; generate a carry when (p & (q-1)) == 0
        cmc
        adc eax,0       ; add 1 to result when (p & (q-1)) != 0
    }
}                       ; eax returned as function value

Ответ 9

Это кажется эффективным и работает для подписанного, если ваш компилятор использует арифметические сдвиги вправо (обычно это правда).

#include <stdio.h>

int main (void)
{
    for (int i = -20; i <= 20; ++i) {
        printf ("%5d %5d\n", i, ((i - 1) >> 1) + 1);
    }
    return 0;
}

Используйте >> 2 для разделения на 4, >> 3, чтобы разделить на 8, & ct. Эффективный lg выполняет там работу.

Вы можете даже разделить на 1! >> 0