Простыми словами о представлении форматов float32 и double64 в памяти компьютера

Форматы float32 и double64 на пальцах

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

Формат float32 имеет такой вид: 1s8e23m, где s — количество бит под знак, e — экспонента, m — мантисса. Для формата double64 вид такой — 1s11e52m.

Первый бит кодирует знак числа. Если это ноль, число положительно, в противном случае число отрицательное.

Затем идут восемь бит экспоненты. Если совсем простыми словами, то экспонента — это количество сдвигов запятой в исходном числе, представленном в двоичном виде, для получения нормализованного числа вида 1.NNN2. Чтобы получить количество сдвигов из этих восьми бит надо отнять 12710. Отрицательная экспонента — сдвиг влево, положительная — сдвиг вправо.

После экспоненты следуют 23 бита мантиссы. Это дробная часть числа 1.NNN2.

А теперь практическая часть!

Перевод десятичной дроби во float32

Попробуем с полученными знаниями закодировать число -2.62510.

В двоичном виде это число имеет вид 10.1012. Для получения нормализованного числа необходимо запятую сдвинуть влево на один разряд. Получим число 1.01012 и экспоненту равной 1.

Для сохранения экспоненты к ней надо прибавить 12710. Получится 12610 или 011111102 в двоичном виде.

Берем нормализованное число 1.01012 и выделяем мантиссу 01012. Для сохранения этого числа, которое занимает 4 бита, надо добавить нули справа до 23 бит. Получится число 010100000000000000000002.

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

Итог: s=12 e=011111102 m=010100000000000000000002, с чем я вас и поздравляю.

Обратный перевод: из float32 в число

Разберем пример из википедии. Есть число во float32 0xC000000016. В двоичной системе это будет 110000000000000000000000000000002.

Разобъем его на компоненты: s=12 e=100000002 m=000000000000000000000002.

Мантисса равна нулю, но, как уже было сказано выше, сохраняется только дробная часть мантиссы, а единица отбрасывается. Значит мантисса равна 1.000000000000000000000002.

Экспонента равна 100000002 или 12810, отнимаем 12710 и получается, что экспонента равна единице.

Возьмем мантиссу и сдвинем точку вправо на эту единицу, получится 10.00000000000000000000002, это 210 в десятичной системе счисления.

Знак числа равен единице, значит исходное число отрицательное.

Решение: -210, что и требовалось доказать.

P.S. Маленькие циферки справа от числа обозначают систему счисления, если кто не знает. Пример: два в десятичной системе — 210, один‑ноль‑один в двоичной системе — 1012. Кстати, красным цветом выделен знак числа, зелёным — экспонента, а мантисса, соответственно, синим.

Полезные ссылки

Самая маленькая программа на C/C++, которая вызывает segmentation fault

Самый маленький код, который после компиляции с помощью gcc вызывает segmentation fault:

main;

Компилируем:

$ gcc crash.c
crash.c:1: warning: data definition has no type or storage class

Запускаем:

$ ./a.out
Segmentation fault

Увидел не так давно на хабре, делюсь.

Почему Thread.sleep() — это прошлый век

Допустим, есть задача: создать поток, который скачивает что-то из интернета, а из основного потока ему валятся задания. Стандартный путь реализации такой:

class DownloadThread extends Thread {
    public interface Listener {
        void onImageLoaded(Image image);
    }
 
    private String reqUrl_ = null;
    private final Listener listener_;
    private boolean isFinished_ = false;
 
    DownloadThread(Listener listener) {
        listener_ = listener;
    }
 
    public void imageRequest(String url) {
        synchronized (this) {
            // Запрос на загрузку изображения
            reqUrl_ = url;
        }
    }
 
    @Override
    public void run() {
        while (!isFinished_)
            String url = null;
 
            synchronized (this) {
                // Проверка: есть ли запрос?
                if (null != reqUrl_) {
                    url = reqUrl_;
                    reqUrl_ = null;
                }
            }
 
            if (null != url) {
                // Запрос есть, загружаем изображение
                Image image = download(url);
                listener_.onImageLoaded(image);
            }
 
            try {
                // Поспим одну милисекунду, чтоб не грузить CPU
                sleep(1);
            }
            catch (InterruptedException e) {
                isFinished_ = true;
                break;
            }
        }
    }
 
    public void stopThread() {
        isFinished_ = true;
    }
}

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

Рассмотрим пример номер два:

class DownloadThread extends Thread {
    public interface Listener {
        void onImageLoaded(Image image);
    }
 
    private String reqUrl_ = null;
    private final Listener listener_;
    private boolean isFinished_ = false;
 
    DownloadThread(Listener listener) {
        listener_ = listener;
    }
 
    public void imageRequest(String url) {
        synchronized (this) {
            // Запрос на загрузку изображения
            reqUrl_ = url;
            // Уведомляем поток, что есть задание
            notify();
        }
    }
 
    @Override
    public void run() {
        while (!isFinished_)
            String url = null;
 
            synchronized (this) {
                if (isFinished_) {
                    break;
                }
                // Проверка: есть ли запрос?
                if (null != reqUrl_) {
                    url = reqUrl_;
                    reqUrl_ = null;
                }
                else {
                    try {
                        // Ждем вызова notify
                        wait();
                    }
                    catch (InterruptedException e) {
                        isFinished_ = true;
                        break;
                    }
                }
            }
 
            if (null != url) {
                // Запрос есть, загружаем изображение
                Image image = download(url);
                listener_.onImageLoaded(image);
            }
        }
    }
 
 
    public void stopThread() {
        synchronized (this) {
            isFinished_ = true;
            notify();
        }
    }
 
}

Почему этот пример лучше первого? Во-первых, когда заданий нет, поток находится в режиме ожидания без вызовов sleep(). Во-вторых, когда задание приходит, поток реагирует моментально просыпаясь.

Обратите внимание, что метод stopThread() слегка изменился. Ввиду того, что поток не выйдет из состояния wait() без вызова notify().

UPD: По совету друзей исправил метод run() для корректного завершения потока.

В обоих примерах не учитывается, что изображения нам нужны пачкой сразу, то есть очередь запросов выкинута для упрощения кода.

P.S. Кстати, в C/C++ для тех же целей можно использовать pthread_cond_wait() и pthread_cond_signal()

Вопросы программисту C/C++ на собеседовании с ответами

Заметил, что на собеседовании часто задают одни и те же вопросы по программированию. Если бы брали на работу водителя, то некоторые вопросы звучат примерно так:

  • В какую сторону надо крутить руль, чтоб повернуть направо?
  • За что отвечает педаль сцепления/тормоза/газа?

Такое конечно случается далеко не всегда, но первые пару вопросов обычно такого рода («А какую надо давить педаль, чтоб автомобиль остановился?»). Публикую свои ответы на некоторые вопросы для программистов. Вдруг кому пригодится.. Возможно, здесь много ошибок и помарок — при составлении этого списка я не пользовался интернетом. Старался выдать, что знаю сам.

Как можно оптимизировать данный цикл?

void func(int *array, int len)
{
    for (int i = 0; i < len; i++)
    {
        array[i] = array[i] * array[i];
    }
}

Вот таким образом:

void func(int *array, int len)
{
    const int *end = array + len;
 
    while (array != end)
    {
        const int value = *array;
        *array++ = value * value;
    }
}

В исходном цикле каждый раз происходит вычисление позиции элемента в массиве array. Переписав функцию мы избавляемся от этого вычисления.

В чем отличие std::list<T> от std::vector<T>?

std::vector<T> — это обертка над обычным С/C++ массивом. Соответственно:

  • если std::vector<T> заполнен, то при добавлении нового элемента, массив удаляется целиком и создается заново с бОльшим размером
  • любой элемент массива можно получить моментально, потому что позиция элемента вычисляется банальным прибавлением индекса к первому элементу (array[i] = array + i)
  • удаление любого элемента из массива, кроме последнего, приведет к перемещению всех элементов справа от удаляемого на одну позицию влево (при соблюдении некоторых условий, можно воспользоваться хаком)
  • занимает неразрывный блок памяти

std::list<T> — это список элементов, которые связаны между собой указателями prev (предыдущий элемент) и next (следующий элемент). Внутри себя std::list<T> хранит указатель на первый элемент и последний (зависит от реализации). Исходя из этого:

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

В языке Java различия между ArrayList и LinkedList практически такие же.

Почему в C++ нужно использовать new вместо теплого лампового malloc()?

Потому что malloc() тупо выделяет блок памяти и возвращает этот блок программисту. А new выделяет память и вызывает конструктор объекта. Тоже самое относится к delete и free(). delete вызывает деструктор и освобождает память. free() просто освобождает память. Также есть размещающий new, который создает объект в уже выделенной вами памяти.

Кстати, изначально конструкторы и деструкторы классов в C++ назывались new и delete и выглядели вот так:

class SomeClass
{
    // Конструктор
    void new();
 
    // Деструктор
    void delete()
};

В чем отличие между new/delete и new[]/delete[]?

new выделяет память для одного элемента и вызывает конструктор для него, в то время как new[] выделяет память для массива элементов и вызывает конструктор для каждого из них. delete должен вызываться для объекта выделенного с помощью new, а delete[] для массива, выделенного с помощью new[]. От проблем соответствия new/delete вас могут избавить классы std::auto_ptr<T> (для одного элемента) и std::tr1::scoped_array<T> (для массива элементов). Которые сами вызывают правильный delete в деструкторе.

Для чего нужен тип std::auto_ptr<T>?

В стародавние времена вы должны были сами следить за тем, чтоб после каждого new был вызван свой delete. Это было жутко неудобно (программисты Си выкручиваются из этой ситуации вставляя goto):

bool func()
{
    Stream *stream = new Stream;
 
    if (0 != stream->open("some stream"))
    {
        delete stream;
        return false;
    }
 
    if (0 != stream->load())
    {
        delete stream;
        return false;
    }
 
    // Выполняем полезную работу
    // Закончили полезную работу
    delete stream;
    return true;
}

После появление std::auto_ptr<T> стало возможным переписать функцию таким образом:

bool func()
{
    std::auto_ptr<Stream> stream(new Stream);
 
    if (0 != stream->open("some stream"))
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }
 
    if (0 != stream->load())
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }
 
    // Выполняем полезную работу
    // Закончили полезную работу
 
    // Здесь "delete stream" вызывается автоматически
    return true;
}

И еще очень важный момент: std::auto_ptr<T> владеет объектом единолично. Вы не сможете шарить объект между двумя std::auto_ptr<T> (используйте в таких случаях std::shared_ptr<T>):

void func() 
{
    Object *object = new Object;
 
    std::auto_ptr<Object> ptr1(object); // object теперь живет внутри ptr1
    std::auto_ptr<Object> ptr2(ptr1); // ptr1 опустел, object внутри ptr2
 
    // здесь деструктор ptr2 удалит object
    // а здесь вызовется деструктор ptr1 впустую
}

И помните: std::auto_ptr<T> не подходит для массивов выделенных с помощью new[]. Для этих целей используйте std::tr1::scoped_array<T> или boost::scoped_array<T>.

Что такое RAII?

Это переводится как «Получение ресурса есть инициализация». Идея вкратце такая: в конструкторе открываем/блокируем ресурс, в деструкторе закрываем/освобождаем ресурс. Вот пример:

class FILEWrap
{
public:
    FILEWrap( const char *fileName )
        : f_(fopen(fileName, "rb"))
    {
    }
 
    ~FILEWrap()
    {
        if (f_)
        {
            fclose(f_);
        }
    }
 
private:
    FILE *f_;
};

Или более каноничный пример (блокирование мьютекса или критической секции):

class MutexLock
{
public:
    MutexLock(Mutex &mutex)
        : mutex_(mutex)
    {
        mutex.lock();
    }
 
    ~MutexLock()
    {
        mutex.unlock();
    }
 
private:
    Mutex &mutex_;
};

Зачем нужен виртуальный деструктор?

Попробуем обойтись без него:

#include <stdio.h>
 
class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }
 
    ~A() 
    { 
        printf("destruct A\n"); 
    }
};
 
 
class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }
 
    ~B() 
    { 
        printf("destruct B\n"); 
    }
};
 
 
int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Вывод:

construct A
construct B
destruct A

Как можно заметить деструктор B не вызвался. Сделаем деструктор класса A виртуальным и посмотрим что получится:

#include <stdio.h>
 
class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }
 
    virtual ~A() 
    { 
        printf("destruct A\n"); 
    }
};
 
 
class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }
 
    ~B() 
    { 
        printf("destruct B\n"); 
    }
};
 
 
int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Теперь все отлично:

construct A
construct B
destruct B
destruct A

В каком порядке инициализируются члены класса?

Члены класса создаются в порядке их объявления в классе. Уничтожаются они в обратном порядке. Давайте проверим:

#include <stdio.h>
 
class Printer
{
public:
    Printer( const char *n ) 
        : n_(n)
    {
        printf("+%s ", n_);
    }
 
    ~Printer() 
    {
        printf("-%s ", n_);
    }
 
private:
    const char *n_;
};
 
 
class A : public Printer
{   
public:
    A() 
        : Printer("A") 
    {
    }
};
 
 
class B : public Printer
{
public:
    B() 
        : Printer("B") 
    {
    }
};
 
 
class C : public Printer
{
public:
    C() 
        : Printer("C") 
    {
    }
};
 
 
class Test
{
private:
    A A_;
    B B_;
    C C_;
};
 
 
int main()
{
    Test test;
}

Запустим:

+A +B +C -C -B -A

Все правильно.

Порядок объявления очень важен, если один член класса во время инициализации использует данные другого члена. Кстати, компилятор gcc выдает warning (с флагом -Wall), если вы описали инициализацию членов класса в другом порядке. И это еще одна причина в пользу использования настройки компилятора «считать предупреждения ошибками» (в gcc это флаг -Werror).

Быстрый способ удаления элемента из массива типа std::vector (C/C++) или ArrayList (Java)

Давно известный прием, но вдруг кто-то не знает: если вам не важен порядок элементов в массиве, то удалить объект из середины массива элементарно — извлекаете последний элемент массива и вставляете его на место удаляемого.

Вот простой код для демонстрации:

#include <vector>
#include <stdio.h>
 
template <class T>
void remove_item( std::vector<T> &v, int i )
{
    // Сохраняем последний элемент
    const T item = v.back();
    // Удаляем последний элемент из массива
    v.pop_back();
    // Вставляем сохраненный элемента вместо элемента с индексом i
    v[i] = item;
}
 
 
int main()
{
    std::vector<int> v;
    v.push_back(10);
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(14);
 
    printf("before:\n");
    for (int i = 0, count = v.size(); i < count; ++i)
    {
        printf("v[%d] = %d\n", i, v[i]);
    }
 
    remove_item(v, 1);
 
    printf("after:\n");
    for (int i = 0, count = v.size(); i < count; ++i)
    {
        printf("v[%d] = %d\n", i, v[i]);
    }
}

Вывод:

before:
v[0] = 10
v[1] = 11
v[2] = 12
v[3] = 13
v[4] = 14
after:
v[0] = 10
v[1] = 14
v[2] = 12
v[3] = 13

Обратите внимание, что в remove_item() происходит копирование последнего элемента. Так что если у вас что-то сложнее простых int, long, char или float, то этот код вам надо переписать.

Код для ArrayList (Java). Не проверял, но идея понятна:

public class ArrayListUtil {
    public static <T> void removeItem(ArrayList<T> v, int index) {
        T item = v.get(v.size() - 1);
        v.remove(v.size() - 1);
        v.set(index, item);
    }
 
    private ArrayListUtil {
    }
}

UPD: В комментариях предложили более лучший способ с использованием std::swap, обратите внимание.