Связанный список интервалов

Question

У меня есть два следующих вопроса.

1. Мне известна концепция связанного списка.Что такое связанный список интервалов?

2. Мне нужно хранить очень большое (более 100 бит) число в C / C ++ и выполнять над ним побитовые операции.Без использования какой-либо библиотеки больших чисел, какая структура данных лучше всего подходит для этого сценария?

Спасибо

Answer 1

1. Имя не звенит ни колокола. Если интервалы являются объектами, то это просто связанный список, в котором хранятся эти объекты. Возможно, вы имеете в виду пропустить список ?
2. Если вы используете C ++, используйте bitset . В противном случае я бы просто использовал классическую таблицу из четырех 32-битных целых.

Answer 2

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

struct interval_node {
      int index;
      struct interval_node* next;
}

, где index хранит все точки, где бит "переворачивается".Это огромное преимущество в памяти, если у вас есть что-то вроде 11111111111100000000000, потому что нужно только сохранить тот факт, что первый бит равен 1 (где-то вне структуры), а также что бит переходит в 12-й индекс (будучиНа основе 0), а не для хранения каждого отдельного бита.Это может масштабироваться до 100 000 бит, не занимая столько памяти, если последовательность не имеет тонны таких вещей, как

1010101010101010101010101010101010101010101010

, потому что она переворачивается на каждый бит.

Answer 3

Если вы хотите написать свой собственный класс для обработки больших битовых чисел (я не знаю, почему вы это сделаете), вы можете обернуть вектор. Вы должны были бы поймать свое собственное переполнение все же. Это огромная боль, и я об этом говорю только потому, что для нас это был последний проект для класса C ++, который я выбрал, лол. Я не рекомендовал это = P

Answer 4

Для второй части вопроса попробуйте std :: bitset