Побитовые сдвиги: Основы и Применение

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

Основные операции побитового сдвига

Левый сдвиг (<<)

Каждый бит числа сдвигается влево на заданное количество позиций.

Пример

1010 << 1 = 10100

Эта операция эквивалентна умножению числа на 2 для каждого сдвига.

Правый сдвиг (>>)

Каждый бит числа сдвигается вправо на заданное количество позиций.

Пример

1010 >> 1 = 0101 = 101

Эта операция эквивалентна делению числа на 2 для каждого сдвига.

---------

Примеры использования:

- Быстрое умножение и деление:
- Маскирование битов
- Шифрование и сжатие данных:

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

Количество установленных битов

Сегодня закрепляем с вами материал по битовым манипуляциям и решаем новую задачу.

Сложность: 🟢 Легкая

ℹ️ Описание

Напишите функцию, которая принимает положительное целое число и возвращает его вес Хэмминга.

⚠️ Ограничения

— Значение n находится в диапазоне от 1 до 2^31 - 1

1️⃣ Пример

Входные данные: n = 11

Ответ: 3

Объяснение: В двоичном представлении число имеет в общей сложности три установленных бита — 1011.

2️⃣ Пример

Входные данные: n = 128

Ответ: 1

Объяснение: В двоичном представлении число имеет в общей сложности один установленный бит — 10000000.

3️⃣ Пример

Входные данные: n = 2147483645

Ответ: 30

Объяснение: В двоичном представлении число имеет в общей сложности тридцать установленных битов — 1111111111111111111111111111101.

✅ Решение через подсчет популяции (Pop Count)

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

Из условия задачи мы знаем, что n может иметь значения в диапазоне от 1 до 2^31 - 1. Это означает, что мы рассматриваем 32-битные числа. То есть число n содержит максимум 32 бита.
Теперь возьмем для примера число 13 и представим его в двоичном виде.

13 -> 1101

Чтобы понять, равен ли определенный бит в числе единице, этот бит нужно умножить на 1 и посмотреть на результат. Если результат равен 1, то и бит тоже равен 1. В противном случае бит равен нулю.
Это определяется правилами побитового умножения. Если в одном операнде всегда стоит единица, то результат операции может быть равен единице только в том случае, если второй операнд тоже равен 1.

0 & 1 = 0
1 & 1 = 1

Это означает, что мы можем пройтись по каждому из 32 битов числа n и умножить его побитово на 1. Если результат равен единице, то мы можем увеличить счетчик установленных битов на 1. После подсчета всех 32 битов мы получим количество установленных битов в счетчике.

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

Мы заведем маску mask, которая на самом деле является целым числом, и счетчик count. Начальное значение mask будет равно 1. Теперь посмотрим на наглядный пример решения.

Представим наше число 13 и маску в двоичном виде и проведем между ними побитовое умножение.

1101 & 0001 = 0001 = 1

В качестве результата получилось положительное число, то есть в первом бите числа n находится единица. Увеличиваем счетчик установленных битов count на 1. Теперь сдвинем единицу в маске на одну позицию влево и сделаем то же самое.

1101 & 0010 = 0000 = 0

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

1101 & 0100 = 0100 = 4

Так в ответе мы получили 4, а не 0, это означает, что на месте единицы в маске в числе n бит также равен единице. Увеличиваем счетчик установленных битов count на 1.

1101 & 1000 = 1000 = 8

По такой же логике мы понимаем, что в старшем бите числа `n` также находится единица. Таким образом мы получили count = 3, то есть в числе n = 13 три установленных бита.

Остался последний вопрос. Как сдвигать единицу в маске? Для этого мы воспользуемся операцией побитового сдвига влево <<.

Посмотреть реализацию в блоге.

🅾️ Оценка сложности

По времени

Так как мы знаем, что число n занимает максимум 32 бита, нам необходимо сделать 32 проверки в цикле. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

#bit_manipulation #easy

✅ Решение через смену младшего установленного бита

Ключевая идея этого решения заключается в том, что при побитовом умножении чисел n и n - 1 младший установленный бит числа n всегда сменяется на 0. При этом все остальные биты остаются неизменными.

Вместо проверки каждого бита числа мы неоднократно обращаем наименее значимый единичный бит числа на 0 и добавляем 1 к нашему счетчику. При этом число n мы заменяем на полученный результат побитового умножения.

Как только число n становится равным 0, мы знаем, что в нем больше не осталось единиц. Это означает, что в нашем счетчике count содержится правильное количество единиц, которые были в битовом представлении числа n.

Посмотреть реализацию в блоге.

🅾️ Оценка сложности

По времени

В худшем случае все биты n являются единичными и мы имеем максимум 32 бита. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

#bit_manipulation #easy

Подсчет битов

Сложность: 🟢 Легкая

ℹ️ Описание

Дано число n.

Верните массив ans длиною n + 1, в котором значение каждого i-го элемента равно количеству единиц в двоичном представлении i.
При этом i находится в диапазоне от 0 до n.

⚠️ Ограничения

— Значение n находится в диапазоне от 1 до 10^5

1️⃣ Пример

Входные данные: n = 2

Ответ: [0, 1, 1]

Объяснение:

Двоичные представления чисел.

0 --> 0
1 --> 1
2 --> 10

2️⃣ Пример

Входные данные: n = 5

Ответ: [0, 1, 1, 2, 1, 2]

Объяснение:

Двоичные представления чисел.

0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

✅ Решение через подсчет популяции (Pop Count)

В качестве решения можно воспользоваться способом подсчета популяции из задачи «Количество установленных битов».

Достаточно вызвать метод hammingWeight для подсчета веса Хэмминга в цикле от 0 до n.

const hammingWeight = (n: number): number => {
    let count = 0

    while (n != 0) {
        count++
        n &= n - 1
    }

    return count
}

export const countBitsPopCount = (n: number): number[] => {
    const res: number[] = []

    for (let i = 0; i <= n; i++) {
        res.push(hammingWeight(i))
    }

    return res
}

✅ Решение через динамическое программирование

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

F(x) = F(x/2) + (x mod 2)

Это формула обозначает, что для получения количества единиц в битовом представлении числа x достаточно взять количество единиц в битовом представлении числа x/2 и прибавить к нему остаток от деления числа x на 2.

Теперь перефразируем эту формулу в битовых выражениях:

операция x / 2 эквивалентна битовому сдвигу на единицу вправо, то есть x >> 1
операция x mod 2 эквивалентна получению младшего бита, то есть x & 1

Общая идея

Мы можем представить число 𝑖 как результат добавления последнего бита к числу 𝑖 >> 1. Если последний бит — единица, то общее количество единиц увеличивается на 1 по сравнению с 𝑖 >> 1, если последний бит — ноль, то количество единиц остается тем же, что и у числа 𝑖 >> 1

Мы запускаем цикл подсчета единиц для каждого числа от 0 до n и каждый результат запоминаем в результирующий массив res. При этом на каждой итерации мы можем опираться на результаты вычислений предыдущих итераций и получать значение для i >> 1 из результирующего массива, так как оно уже было рассчитано раньше.

Посмотреть реализацию в блоге

#bit_manipulation #easy

Односвязный список (Singly Linked List)

Односвязный список — это структура данных, которая позволяет делать последовательность элементов, где каждый элемент имеет указатель на следующий элемент в списке.

Вот пример типичной структуры узла односвязного списка.

type MyLinkedListNode = {
    val: number;
    next: MyLinkedListNode | null;
}

type MyLinkedListNode struct {
    Val  int
    Next *MyLinkedListNode
}

У связанных списков всегда есть первый элемент списка, который называется head (голова) и последний элемент — tail (хвост). Чтобы предоставить весь список достаточно иметь ссылку на его голову, так как путем последовательного перебора узлов черерз next можно проитерироваться по всему списку.

В нашем примере ниже в качестве головного выступает элемент со значением 1. От него можно перейти по ссылке к следующему элементу со значением 2 и уже от него к хвостовому элементу со значением 3.

Следствием такой организации структуры данных являются несколько важных особенностей работы односвязного списка.

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

2. Еще проще работает удаление первого элемента и тоже за константное время. Для удаления достаточно переписать ссылку на head ссылкой на head.next. Соответственно, это тоже работает за константное время.

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

4. Все операции в связном списке имеют константную сложность по памяти, так как для их выполнения достаточно оперировать ссылками на элементы.

#linked_list

Пример односвязного списка

#linked_list

Проектирование связанного списка

Привет, друзья. Теперь мы с вами закрепим теорию, которую узучили ранее и реализуем связанный список с нуля.

Сложность: 🟡 Средняя

ℹ️ Описание

Разработайте свою реализацию связанного списка. Вы можете использовать одно- или двусвязный список.

Узел в односвязном списке должен иметь два атрибута: val и next.

val — значение текущего узла
next — указатель/ссылка на следующий узел

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

Реализуйте класс MyLinkedList:

— MyLinkedList() инициализирует объект MyLinkedList.
— int get(int index) метод позволяет получить значение узла в списке по его индексу. Если индекс неверный, метод должен возвращать -1.
— void addAtHead(int val) метод позволяет добавлять узел со значением val в начало списка.
— void addAtTail(int val) метод позволяет добавлять узел со значением val в конец списка.
— void addAtIndex(int index, int val) метод позволяет добавлять узел со значением val на место элемента с индексом index. Если индекс равен длине связанного списка, узел будет добавлен в его конец. Если индекс больше длины списка, то его добавлять не нужно.
— void deleteAtIndex(int index) метод позволяет удалить элемент под индексом index из списка.

⚠️ Ограничения

— Значения каждого элемента списка находятся в диапазоне от 0 до 1000
— В списке может быть от 0 до 1000 элементов

1️⃣ Пример

// псевдокод
myLinkedList = MyLinkedList();
myLinkedList.addAtHead(1);        // [1]
myLinkedList.addAtTail(3);        // [1, 3]
myLinkedList.addAtIndex(1, 2);    // [1, 2, 3]
myLinkedList.get(1);              // 2
myLinkedList.deleteAtIndex(1);    // [1, 3]
myLinkedList.get(1);              // 3

✅ Реализация односвязного списка

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

Для начала опишем простой класс MyLinkedList с инициализирующим конструктором и создадим пустые методы-заглушки.

type MyLinkedListNode = {
    val: number;
    next: MyLinkedListNode | null;
}

export class MyLinkedList {
    head: MyLinkedListNode | null;
    size: number;

    constructor() {
        this.head = null;
        this.size = 0;
    }

    get(index: number): number {
        return 0
    }

    addAtIndex(index: number, val: number): void {}

    addAtHead(val: number): void {}

    addAtTail(val: number): void {}

    deleteAtIndex(index: number): void {}
}

Здесь мы сразу описали тип MyLinkedListNode для одной ноды списка и сам класс.

Во-первых, в классе мы завели переменную head, которая по умолчанию равна null. Это и есть ссылка на голову списка, то есть на его первый элемент.

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

🔸Получение элемента из списка

Метод предназначен для получения значения узла по указанному индексу.

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, возвращается -1, так как такой индекс недопустим.

Далее необходимо пройти по списку от его головы и найти элемент с нужным индексом. Для этого мы запускаем цикл, который выполняется до тех пор, пока i < index. Инициализируем переменную curr, которая изначально равна head то есть ссылке на первый элемент списка. Далее на каждой итерации цикла в переменную curr записывается ссылка на следующий элемент в списке через curr.next.

Если удалось найти нужный элемент в списке, то возвращаем его значение в качестве ответа, иначе возвращаем -1.

🔸Добавление элемента в список по индексу

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, то выходим из функции и не выполняем вставку.

Следующим шагом увеличиваем внутреннюю переменную size на единицу, так происходит добавление элемента.

Если индекс равен 0, то происходит вставка в начало списка. Это означает, что нам достаточно создать новый элемент, указать в его next ссылку на текущий head списка и заменить текущий head новым элементом, после чего выйти из функции.

Если же индекс не равен 0, то нам нужно добавить элемент перед тем, который находится на позиции равной index. Мы выделили отдельный внутренний метод findPrevNode. Вызвав этот метод мы получаем предшествующий переданному индексу узел prev. Если такой узел существует, то нам достаточно в next нового элемента добавить ссылку из prev.next, а в prev.next положить ссылку на новый элемент. Таким образом новый элемент встраивается в цепочку узлов списка на заданную позицию.

🔸Добавление элемента в начало списка

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в начало. Для этого просто вызовем метод с нулевым индексом this.addAtIndex(0, val)

🔸Добавление элемента в конец списка

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в конец. Для этого просто вызовем метод с индексом равным длине списка this.addAtIndex(this.size, val)

🔸Удаление элемента

В первую очередь нужно проверить корректность индекса. Если индекс меньше 0 или больше или равен размеру списка, метод завершает работу, так как такой индекс некорректен.

Далее необходимо уменьшить значение переменной size на единицу, так как происходит удаление.

Если индекс равен нулю, значит происходит удаление первого элемента. В этом случае достаточно изменить head списка на head.next.

Если же индекс не равен нулю, то нужно сначала найти элемент, который находится перед удаляемым. Затем нужно проставить ссылку с предыдущего на следующий элемент prev.next = prev.next.next.

Посмотреть реализацию в блоге

#linked_list #medium

Префиксное дерево (Trie)

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

Вот пример структуры узла Trie.

type TrieNode = {
    children: { [key: string]: TrieNode };
    isEndOfWord: boolean;
}

type TrieNode struct {
    Children    map[rune]*TrieNode
    IsEndOfWord bool
}

Каждый узел имеет мапу children, где ключом является символ, а значением — следующий узел, представляющий символ в этом слове. Узел isEndOfWord помечает конец слова.

Простыми словами, если мы хотим добавить слова «cat» в дерево, нам нужно разбить его посимвольно и каждый символ будет представлять собой отдельную ноду. Иерархия нод будет выстроена в соответствии с порядком слов, то есть в нашем примере: «c» -> «a» -> «t».

Вот так можно визуализировать префиксное дерево, в котором содержаться слова cat, car, cart, care, dog, dot, и dove:

           (root)
         /        \
        c          d
       /           |
      a            o    
     / \         / | \
   t*   r*      g* t* v
       / \            |
     e*  t*           e*

### Пример работы с Trie

Допустим, мы хотим сохранить слова «cat» и «car». Префиксное дерево будет выглядеть следующим образом:

1. Корневой узел содержит ссылки на узлы c, которые ведут к поддереву для символа a.
2. Узел a ветвится на узлы t и r, представляющие слова «cat» и «car».
3. В узлах t и r флаг isEndOfWord установлен в true, указывая, что здесь заканчиваются слова.

### Основные операции в Trie

1. Добавление слова — добавление слова в Trie выполняется за O(N), где N — длина слова. Мы последовательно проходим каждый символ слова и либо создаем новый узел, если он не существует, либо переходим к существующему.

2. Поиск слова — поиск также выполняется за O(N). Для поиска слова достаточно пройти по каждому символу слова. Если на каком-то этапе путь отсутствует, значит, слово не найдено.

3. Поиск по префиксу — уникальная особенность Trie. Чтобы найти все слова, начинающиеся с заданного префикса, можно просто дойти до конца префикса, а затем собрать все слова, начиная с этого узла.

### Преимущества и недостатки Trie

1. Trie отлично подходит для поиска по префиксам и проверки принадлежности слова к множеству. Это особенно полезно в задачах автодополнения и саджестов. Более того, я сталкивался с этой структурой в реальных сервисах - именно для реализации быстрого саджеста.

2. Относительно экономное потребление памяти для хранения словарей — общие префексы не дублируются, в отличии от варианта, если бы мы хранили тот же словарь в виде обычного массива. В реальных словарях количество слов ограничено и многие слова имеют общие префиксы.

3. Недостатком является узкая специализация данной структуры. Данная структура позволяет искать только по точному совпадению префикса. То есть, например, если вам нужно искать слово не по префиксу, а по любой возможной подстроке, или учесть опечатки — классический Trie становится бесполезным. Не смотря на то, что некоторые модификации данной структуры могут решить часть проблем, не факт что данная структура будет оптимальным выбором для решения подобных задач.

#trie

Disjoint Set

Привет, друзья!

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

Представим, что перед нами есть карта, на которой схематично обозначены 8 городов. При этом, города 0, 1, 2 и 3 соединены между собой дорогами. Города 4, 5 и 6 также соединены между собой, а город 7 обособлен и не имеет сообщения с другими.

Таким образом города являются вершинами графов, а дороги — их ребрами.

Города могут иметь прямое соединение, как например 4 и 6, или же транзитивное как в случае 0 и 3. В результате мы имеем три непересекающихся множества:

— [0, 1, 2, 3]
— [4, 5, 6]
— [7]

Теперь нам нужно построить эффективную структуру, которая позволит быстро понимать, соединены ли два города между собой, и даст возможность объединять два непересекающихся множества в одно.

Для подобных задач можно использовать структуру данных Disjoint Set, которую также иногда называют Union Find.

Базовая реализация

Базово такая структура данных должна поддерживать три основных метода

find(x int) int

find — Находит рутовый элемент в множестве для указанного узла;

union(x int, y int)

union — Объединяет два множества путем соединения двух вершин в них между собой;

connected(x int, y int)

connected — Проверяет соединены ли две вершины графа между собой, то есть входят ли они в одно множество.

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

- В первом множестве решим, что рутовым узлом будет город с номером 0. Он же является рутовым узлом для самого себя.
- Во втором множестве выберем город с номером 4. Он также является рутовым узлом для самого себя.
- Семерка ни с чем не связана, поэтому она является рутовым узлом в своем множестве.

Таким образом для нашего случая массив должен иметь следующий вид.

[0, 0 , 0, 0, 4, 4, 4, 7]

Поиск

Теперь не сложно догадаться, что для реализации поиска достаточно получить индекс рутового узла для конкретного города по его индексу в массиве.

Проверка связности

Проверка связности тоже реализуется крайне легко. Нужно получить рутовые элементы для города x и y при помощи метода find и сравнить их. Если два города имеют один и тот же рутовый город в графе, то они связаны либо напрямую, либо транзитивно.

Объединение множеств

Теперь предположим, что нам нужно соединить города с номерами 3 и 4, тем самым объединив первое и второе множества.

Мы решаем, что у объединенного множества родительский элемент остается равным 0. Это означает, что города с номерами 3, 4 и 5 должны получить связь с ним, то есть обновить значение своего рутового узла на 0.

Таким образом наш массив должен получить следующие значения.

[0, 0 , 0, 0, 0, 0, 0, 7]

Теперь осталось имплементировать структуру данных по описанной логике.

Подробную реализацию можно посмотреть в нашем блоге

#disjoint_set #graph