Хитрости программиста

Арифметика и логика

Округление

Существует множество видов округлений, начиная от простого отбрасывания незначимой части, заканчивая хитрыми симметричными методами. Приму следующие названия для типов округления:

  • вниз (иначе называемое к минус-бесконечности) — округление до наибольшего круглого числа меньше или равного данному.
  • вверх (иначе: к плюс-бесконечности) — округление до наименьшего круглого числа, больше или равного данному.
  • к ближайшему — округление до числа, модуль разности которого с исходным минимален.
  • симметричное (обычно относится к округлению к ближайшему) — округление, не смещающее математическое ожидание.
  • к нулю — округление вниз для положительных чисел и вверх для отрицательных.
  • от нуля — округление вверх для положительных чисел и вниз для отрицательных.

В этом разделе я буду использовать следующие обозначения:

  • Q — квант округления, то есть число, до кратного которому округляется исходное число.
  • floor(x) или x — округление вниз до целого.
  • ceil(x) или x — округление вверх до целого.

Округление при сдвигах вправо

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

Примем условное обозначение:

  • N — число битов, на которые производится сдвиг.

При этом подразумевается, что

  • Q = 2N,

то есть сдвиг производит округление до степени двойки, причём показатель степени равен числу битов.

Округление вниз

Тут не надо ничего городить — в арифметике со дополнением до двух при сдвиге влево округление вниз происходит само собой.

y = x >> N;
Округление вверх

Окгругление вверх тоже достаточно просто, его можно совершить двумя простыми способами:

Обычный способ
здесь к округляемому числу сначала прибавлятся число, содержащее единицы во всех выдвигаемых разрядах, так что за счёт переноса результат увеличится на 1.
y = (x+(1 << N-1)-1)>>N
Короткий способ
суть в том, что меняя знак, округление вниз можно превратить в округление вверх, и наоборот.
y = -(-x >> N)

Манипуляции с битами

Полезные константы

Установлен бит N
1<<N

Установлено N младших битов (N-1…0)

(1<<N)-1

Подсчёт количества битов

Наивный метод
простой цикл по битам
  for(i = 0, S = 0; x<0; x>>1) {
    if(x&1!=0) S++;
  }

Сброс всех битов, кроме младшего

Хороший метод
x&-x

Номер установленного бита

Наивный метод
аналогично подсчёту
Сложный метод на макросах языка С
находит номер младшего установленного бита
#define bitno_mod9(b) ((((b)&-(b))%7>>1)+3*(((((b)&-(b))>>2)*7&011111111111)%0777%6>>1))
#define bitno(b) (bitno_mod9(b)+9*bitno_mod9(((((b)&-(b))>>8)*0777&01001001001)%0776))

Преобразование между различными системами счисления

Перевод в десятичную систему

Вот две функции преобразования целого числа без знака, обладающие парой преимуществ:

  1. не используют такую длительную операцию как деление (в отличие от классических, которые делают его каждый разряд;
  2. используется только короткое умножение на константу (16×8 или 32×16) быстро вычисляемое на большинстве архитектур или приводимое к серии сдвигов.
  3. получают цифры в порядке их следования в записи (т. е. слева направо), то есть не требуют переворачивания строки.

Конечно, здесь показан сырые варианты, ограниченный размером числа и выводящий всегда одинаковое число знаков, но её несложно расширить и адаптировать.

16-битная версия (ограничение до 999).

char * strfu3(char *str, unsigned int x) {
    int i;
    x = (x<<2) + ((25*x)>>8) + 2;                      // x*(2**12/10**3)
    for(i = 0; i<3; i++) {
        x = x * 10;
        *(str++) = '0' + (x>>12);
        x &= 0xFFF;
    }
    *str = 0;
    return str;
}

32-битная версия (ограничение до 999999).

char * strfu6(char *str, unsigned int x) {
    int i;
    x = (x<<8) + ((3183*x)>>8) + 128;                  // x*(2**28/10**6)
    for(i = 0; i<6; i++) {
        x = x * 10;
        *(str++) = '0' + (x>>28);
        x &= 0xFFFFFFF;
    }
    *str = 0;
    return str;
}

Языковые пируэты

С-подобные языки

Наивная (каноническая) запись Гик-запись Комментарий
NULL 0 Совершенно законно, ибо постандарту NULL=(void *)0
if(0!=x) if(x) if сравнивает результат с нулём всегда
0==x !x Кроме указателей?
0!=x !!x Если x — условие, то просто x
if(!f) y++ y += !f Точно так же – и =-
if(f) y++ y += f
f?a:0 -x&a
f?a:b b^-x&(a^b)
cifra/xitrosti_programmista.txt · Последние изменения: 2010/08/24 21:00 — vovanium
За исключением случаев, когда указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution 3.0 Unported