Базовые и битовые операции в компьютерах

Почему компьютеры считают в двоичном формате:

Компьютеры состоят из схем, а схемы имеют только два состояния: 0 и 1.

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

В десятичной дроби 1 в разряде единиц означает 10⁰=1, 1 в разряде десятков означает 10¹=10, а 1 в разряде сотен означает 10²=100, поэтому: 123=1×10²+2×10¹+3×10⁰

Точно так же в двоичном формате 1 в одном разряде представляет 2⁰=1, 1 в разряде десятков представляет 2¹=2, а 1 в разряде сотен представляет 2²=4, поэтому: (A3A2A1A0)₂=A3 ×2³+A2×2²+A1 ×2¹+A0×2⁰

Если двоичные и десятичные числа встречаются в одном и том же уравнении, чтобы различать их, мы используем форму (A3A2A1A0)₂, чтобы указать, что A3A2A1A0 является двоичным числом, и каждое число может быть только 0 или 1. Другие числа без скобок и нижних индексов по-прежнему представлять десятичное число. Для двоичного числа, такого как (A3A2A1A0)₂, крайний левый бит A3 называется старшим значащим битом (MSB, старший значащий бит), а крайний правый бит A0 называется младшим значащим битом (LSB, младший значащий бит). Отныне мы следуем этому соглашению:LSB называется 0-м битом, а не 1-м битом, поэтому, если число состоит из 32 бит, MSB является 31-м битом.. Приведенная выше формула является формулой преобразования из двоичного в десятичное число.

Давайте посмотрим, как преобразовать десятичное число в двоичное. мы знаем

13=1×2³+1×2²+0×2¹+1×2⁰ Таким образом, 13, преобразованное в двоичное, должно быть (1101)₂. Вопрос в том, как разложить 13 в виде справа от знака равенства? Обратите внимание, что правая часть знака равенства может быть записана как

13=(((0×2+1₃)×2+1₂)×2+0₁)×2+1₀

Мы можем извлечь четыре числа 1101 из приведенной выше формулы, многократно разделив 13 на 2 и взяв остаток. подписываются следующие формулы:

13÷2=6...1₀ 6÷2=3...0₁ 3÷2=1...1₂ 1÷2=0...1₃

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

Компьютеры используют двоичный код для представления чисел, и программисты также должны привыкнуть к использованию двоичного кода, но двоичный код слишком многословен для записи, поэтому двоичные числа обычно делятся на группы из трех или четырех цифр, и каждая группа представлена числом. Например, разделите (10110010)₂ на группы по три цифры, начиная с самой младшей цифры, 10, 110, 010, а затем запишите каждую группу в виде десятичного числа, то есть (262)₈, чтобы диапазон значений каждой цифры это 0~7, каждые восемь и один, называемый восьмеричным (Octal). Аналогично разделим (10110010)₂ на группы по четыре цифры, 1011, 0010, а затем каждую группу запишем в виде числа Младшая цифра этого числа 2, а старшая цифра уже больше 9. Оговариваем, что буквы A ~ F представляют 10 ~ 15. Это число может быть записано как (B2)₁₆, диапазон значений каждой цифры 0 ~ F, каждое шестнадцатеричное число равно единице, называемой шестнадцатеричной (шестнадцатеричной). Поэтому восьмеричный и шестнадцатеричный — это удобные способы записи, придуманные программистами для удобства написания двоичного, точно так же, как отношения между курсивом и печатными буквами.

Битовая операция:

Целые числа представлены в компьютере двоичными битами.В языке C есть несколько операторов, которые могут напрямую манипулировать битами целых чисел, которые называются битовыми операциями.

1.1 Побитовое И, ИЛИ, XOR, Отрицание

Побитовое И (&): оба операнда равны 1, результат равен 1, иначе 0
или (|): оба операнда имеют 1, результат равен 1
XOR (^): если два операнда одинаковы, результат равен 0, а если два операнда разные, результат равен 1.
Отрицание (~): отрицание операнда

1.2. Сменная работа

Операторы сдвига (побитовый сдвиг) включают сдвиг влево >. Сдвиг влево сдвигает все двоичные биты целого числа влево на несколько битов, например, 0xcffffffff3

Платформа Java представляет собой все целые числа со знаком, поэтому приведенная выше операция на рис. 1 изменяет бит знака в Java с (-805306381) на (1073741772).

В определенном диапазоне значений сдвиг целого числа влево на 1 бит эквивалентен умножению на 2.. Например, двоичное число 11 (десятичное число 3) смещается влево и становится равным 110, то есть 6, а затем сдвигается влево, получая 1100, то есть 12. Читатели могут сами убедиться, что это правило выполняется как для чисел со знаком, так и для чисел без знака, а также для отрицательных чисел. Конечно, если сдвиг влево изменяет старший бит (бит знака), то результат не должен умножаться на 2, поэтому я добавил поправку"в пределах определенного диапазона значений". Поскольку компьютер выполняет сдвиг намного быстрее, чем умножение, компилятор может воспользоваться этим для оптимизации, например, увидеть i*8 в исходном коде, который может быть скомпилирован в инструкции сдвига вместо инструкций умножения.

Когда операнд представляет собой число без знака, правила операции сдвига вправо аналогичны правилам сдвига влево, например, 0xcffffff3>>2 получает 0x33fffffc:

Результат выполнения на платформе Java: значение изменяется с -805306381 на -201326596 и по-прежнему сохраняет бит знака отрицательного числа, что эквивалентно делению на 4

11 из двух младших битов сдвигаются наружу, два старших бита заполняются двумя нулями, а остальные биты сдвигаются вправо на два бита по очереди. Как и при сдвиге влево, количество сдвинутых битов должно быть меньше, чем общее количество битов в левом операнде, иначе результат будет неопределенным. В пределах определенного диапазона значений сдвиг целого числа вправо на 1 бит эквивалентен делению на 2 с усечением дробной части.

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

Если это положительное число, введите 0 в старший бит
Если это отрицательное число, не обязательно, является ли старший бит 1 или 0, что определяется реализацией. Для компилятора gcc платформы x86 старший бит вводится в 1, то есть по-прежнему сохраняется знаковый бит отрицательного числа. Этот метод обработки по-прежнему сохраняет свойство «сдвиг на 1 бит вправо эквивалентен делению на 2" для отрицательных чисел.

Подводя итог, очень неудобно использовать числа со знаком для битовых операций из-за проблем с преобразованием типов и сдвигом, поэтомуРекомендуется выполнять побитовые операции только с беззнаковыми числами, чтобы уменьшить вероятность ошибок..

1.3 Маска:

Если вы хотите работать с некоторыми битами в целом числе, как представить положение этих битов в целом числе? Его можно представить маской. такие как маска0x0000ff00Указывает, что операции выполняются с 8~15 битами 32-битного целого числа, например, следующим образом.

1. Выньте 8~15 цифр.

unsigned int a, b, mask = 0x0000ff00;
a = 0x12345678;
b = (a & mask) >> 8; /* 0x00000056 */

2. Очистить биты с 8 по 15 до 0.

unsigned int a, b, mask = 0x0000ff00;
a = 0x12345678;
b = a & ~mask; /* 0x12340078 */

3. Установите 8~15 на 1.

unsigned int a, b, mask = 0x0000ff00;
a = 0x12345678;
b = a | mask; /* 0x1234ff78 */

Применение битовой операции в алгоритме снежинки:

Максимальное значение 12-битного приращения в миллисекундах: 1 сдвиг вправо 12 бит минус 1, вы можете использовать пропорциональную последовательность для вычисления максимального значения следующих 12 бит, чтобы увидеть, согласуется ли оно с результатом смещения; двоичное представление: (...001111 1111 1111) (0 с после 14 заменяются многоточием)
10bits Worker Process Id: 1 сдвигается вправо на 10 бит, вот у меня вопрос, 1 не надо вычитать, это максимальное значение?
Основание для принятия решения о получении в следующий раз:0L == (sequence = ++sequence & SEQUENCE_MASK)последовательность и максимальное значениепобитовое И, только когда последовательность больше, чем SEQUENCE_MASK, результат & равен 0, получить следующую метку времени
41 бит: (currentMillis - EPOCH)
((currentMillis - EPOCH)

Реализация shrding-jdbc по умолчанию:


/**
 * 默认的主键生成器.
 * 
 * <p>
 * 长度为64bit,从高位到低位依次为
 * </p>
 * 
 * <pre>
 * 1bit   符号位 
 * 41bits 时间偏移量从2016年11月1日零点到现在的毫秒数
 * 10bits 工作进程Id
 * 12bits 同一个毫秒内的自增量
 * </pre>
 * 
 * <p>
 * 工作进程Id获取优先级: 系统变量{@code sharding-jdbc.default.key.generator.worker.id} 大于 环境变量{@code SHARDING_JDBC_DEFAULT_KEY_GENERATOR_WORKER_ID}
 * ,另外可以调用@{@code DefaultKeyGenerator.setWorkerId}进行设置
 * </p>
 * 
 * @author gaohongtao
 */
@Getter
@Slf4j
public final class DefaultKeyGenerator implements KeyGenerator {
    
    public static final long EPOCH;
    
    public static final String WORKER_ID_PROPERTY_KEY = "sharding-jdbc.default.key.generator.worker.id";
    
    public static final String WORKER_ID_ENV_KEY = "SHARDING_JDBC_DEFAULT_KEY_GENERATOR_WORKER_ID";
    
    private static final long SEQUENCE_BITS = 12L;
    
    private static final long WORKER_ID_BITS = 10L;
    
    private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;
    
    private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;
    
    private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;
    
    private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS;
    
    @Setter
    private static TimeService timeService = new TimeService();
    
    @Getter
    private static long workerId;
    
    static {
        Calendar calendar = Calendar.getInstance();
        calendar.set(2016, Calendar.NOVEMBER, 1);
        calendar.set(Calendar.HOUR_OF_DAY, 0);
        calendar.set(Calendar.MINUTE, 0);
        calendar.set(Calendar.SECOND, 0);
        calendar.set(Calendar.MILLISECOND, 0);
        EPOCH = calendar.getTimeInMillis();
        initWorkerId();
    }
    
    private long sequence;
    
    private long lastTime;
    
    public static void initWorkerId() {
        String workerId = System.getProperty(WORKER_ID_PROPERTY_KEY);
        if (!Strings.isNullOrEmpty(workerId)) {
            setWorkerId(Long.valueOf(workerId));
            return;
        }
        workerId = System.getenv(WORKER_ID_ENV_KEY);
        if (Strings.isNullOrEmpty(workerId)) {
            return;
        }
        setWorkerId(Long.valueOf(workerId));
    }
    
    /**
     * 设置工作进程Id.
     * 
     * @param workerId 工作进程Id
     */
    public static void setWorkerId(final long workerId) {
        Preconditions.checkArgument(workerId >= 0L && workerId < WORKER_ID_MAX_VALUE);
        DefaultKeyGenerator.workerId = workerId;
    }
    
    /**
     * 生成Id.
     * 
     * @return 返回@{@link Long}类型的Id
     */
    @Override
    public synchronized Number generateKey() {
        long currentMillis = timeService.getCurrentMillis();
        Preconditions.checkState(lastTime <= currentMillis, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, currentMillis);
        if (lastTime == currentMillis) {
            if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
                currentMillis = waitUntilNextTime(currentMillis);
            }
        } else {
            sequence = 0;
        }
        lastTime = currentMillis;
        if (log.isDebugEnabled()) {
            log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
        }
        return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
    }
    
    private long waitUntilNextTime(final long lastTime) {
        long time = timeService.getCurrentMillis();
        while (time <= lastTime) {
            time = timeService.getCurrentMillis();
        }
        return time;
    }
}

наконец:

У Little Tail есть волна, добро пожаловать, чтобы обратить внимание на мой публичный аккаунт и время от времени делиться своими мыслями о программировании, инвестициях и жизни :)