Могу ли я предположить, что побитовая операция И равна O(1)? Если да, то почему?

Короткий ответ:

Да, одно побитовое И будет считаться O(1).

Подробнее:

Даже если вы посмотрите на количество операций над каждым битом, оно все равно будет O(1). Фактическое количество битовых операций может варьироваться в зависимости от типа переменной, например. 8 бит против 16 бит против 32 бит против 64 бит (даже 128 бит или больше). Ключ в том, что независимо от того, что использует базовая машина, она все равно будет выполнять constant операций для ее выполнения. Таким образом, даже по мере развития компьютеров побитовое И по-прежнему будет O(1).

Еще один пример для уточнения

Следующий блок кода — O(1):

print('Hello World');
print('Hello World');
print('Hello World');

Хотя мы печатаем hello world 3 раза, каждый раз, когда мы запускаем его, для запуска и работы требуется постоянное количество времени, и это не займет больше времени, если кто-то введет в программу большой набор данных. Он просто напечатает 3 вещи, независимо от ввода.

В случае побитового И мы выполняем определенное количество подопераций, число которых всегда одинаково. например 8, 16, 32 и т. д. для одной операции, но она всегда одинакова или постоянна.

В вашем примере похоже, что вы пытаетесь показать, что у вас есть некоторые операции, которые также не требуют выполнения всех битов. Даже если эти меньшие операции учитывали только 4 бита, скажем, 8. Ваш код всегда просто выполнял бы постоянное количество операций, когда попадал бы в этот код. Это все равно, что печатать 4 оператора hello world вместо 8 операторов hello world. В любом случае, 4 или 8 отпечатков, это все равно постоянно.

Вот почему одна побитовая операция И — это O(1).

Сначала о доп. Большинство ЦП имеют так называемый флаг переноса в каком-либо регистре состояния процессора, который позволяет вам обнаруживать сложение и вычитание, превышающее битовый размер регистра. Поэтому узнайте размер регистров на вашем конкретном процессоре, чтобы определить пропускную способность шины данных, а затем узнайте, как вы можете проверить флаги регистров состояния. Для этой цели большинство ЦП будет иметь SUB и ADD с переносом и без него.

Далее, о временной сложности: вы не можете использовать для этого нотацию Big O. Вам нужно выяснить, сколько циклов требуется ЦП для выполнения операции в абсолютном времени (частота * циклы), затем вам нужно принять во внимание другие вещи, такие как доступ к памяти по сравнению с доступом к кешу L1 и L2, чтобы выяснить общее время операции возьмет за этот процессор.

Наконец, доступ к памяти из ассемблерного кода (как вы, кажется, подразумеваете) позволяет вам быть намного более эффективным, чем с языками более высокого порядка, такими как Python. ЦП будет включать в себя инструкции, которые могут настроить адресацию памяти в соответствии с размером того, что вы ищете. C-подобные языки также будут иметь такую ​​возможность, но Python — нет. В JavaScript даже нет целых чисел, но я отвлекся...

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

У вас, видимо, есть некоторое замешательство в отношении того, что означает O(...).

1. нотация big-O требует переменной; например, известно, что сортировка с использованием сравнения и замены элементов массива из n не меньше O(n*log(n)), и у вас есть n, то есть переменная: as n > Увеличение времени сортировки также будет увеличиваться еще быстрее. Говоря, что x & 0xFF равно O(1), о какой переменной вы говорите?

2. big-O — это абстрактные алгоритмы, в которых n может расти до бесконечности. Если n и компьютер ограничены верхней гранью, то любой алгоритм либо не завершается, либо ограничен константой (о пределе чего-то, как , говорить не имеет смысла n увеличивается до бесконечности, если n не может превышать определенный предел).

Когда речь идет о низкоуровневых аппаратных операциях, все операции выполняются за O(1). Некоторые из них быстрее и требуют всего один «шаг» (например, очистка регистра), некоторые требуют больше шагов (например, целочисленное деление). Однако даже деление займет не более n шагов, где n — небольшое целое число.

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

Это то, что Кнут делает в TAOCP.

PS: к сожалению, современные процессоры настолько сложны, что подсчет циклов больше не работает в реальном мире. Например, они могут разбивать инструкции на микроинструкции, перепланированные для параллельного выполнения, они поддерживают спекулятивное выполнение с возвратом, прогнозированием ветвлений и другими трудными для анализа методами. Вдобавок ко всему, существует проблема кэширования, которая сегодня чрезвычайно важна, и разные, но совместимые модели могут иметь совершенно разные подходы. Единственный способ действительно узнать, сколько времени требуется для выполнения фрагмента кода с современными процессорами, — это просто запустить и измерить его на реальных данных для конкретной модели процессора и оборудования.

В целях:

1. Нет. Если ваш процессор может выполнять 8- или 16-разрядные операции, это может быть 8- или 16-разрядный процессор. На самом деле, скорее всего, это будет 8 бит, так как большинство процессоров пытаются обрабатывать операции двойного размера.

2. Да, О(1). Но не потому, что это аппаратно, а потому, что аппаратно реализован O(1). Кроме того, имейте в виду, что все O(x) на самом деле «умножены на константу». Таким образом, если что-то равно O(16), это действительно O(1), умноженное на константу 16.

Наконец, если у вас есть 16-битное слово и вам нужны младшие биты, а ваш процессор действительно поддерживает 8-битные операции, вы, вероятно, можете получить доступ к младшим битам с помощью инструкции MOV. Что-то типа:

mov16 ax, (memory)
mov8  (othermemory), al

Если это недоступно, и вам нужно выполнить И, тогда да, И будет O (1), потому что это почти наверняка аппаратно. Даже если нет, в худшем случае это, вероятно, O (8), и это действительно псевдоним для O (1).