Вы написали — из первой части, то есть, из младшей. У нас с Вами конфликт обозначений) Поэтому предлагаю употреблять термины «старший» и «младший», как не подлежащие сомнению.
Но если серединное слово ненулевое — то тоже надо продолжать поиск в старшей части. Перейти к младшей можно, только проверив всю старшую половину.
Цитата из поста:
«На всякий случай, поясню: старшим битов называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа.»
Здесь, разумеется, имеется в виду само по себе натуральное число, а не то, сколько места оно занимает в памяти.
Да) Я, когда об этом задумался, сначала понял, что все три алгоритма с успехом модифицируются для поиска младшего бита, а потом сообразил, что с младшим всё гораздо проще)
Знаем, конечно.
Так, ещё раз. В статье шла речь о числах от 1 до 2^31-1. То есть, о тех, у кого единичными могут быть только биты от 0-го до 30-го. В упомянутом Вами числе единственный ненулевой бит — 32-ой. Значит, не будет ни одного бита, который был бы единичным и в х, и в 2^32. Значит, все биты выражения x & (2^32) будут нулевыми. То есть, результат этого выражения будет равен нулю.
Ну да) Для слишком больших типов (уже для 32-х битных) табличка будет уже слишком большой — это и есть специфический минус =)
Но и Вы правы, да. В зависимости от ситуации, возможно, можно сделать и для двух байтов табличку.
Круто, спасибо за такой подробный комментарий, было интересно.
Правда, как уже заметили ruguevara и mephisto, сточки зрения алгоритма — этот, по сути, такой же, как первый.
Мне лично минимальное время считать сложнее, поскольку java не очень точна, когда меряешь маленькое время, значит, нужно делать много раз каждый тест, и, желательно, много тестов, по секунде на тест — это долго.
Ну, пусть мы будем рассматривать long (или long long в С++, короче, 64-битный тип. Иначе 2^32 == 0).
Тогда ваше выражение выдаёт два возможных ответа: 0 или 2^32. Очевидно, что возможных ответов в этой задаче гораздо больше.
& — это побитовое логическое И, не так ли?
О, я так не понимаю. Буду рад, если Вы поясните) Особенно фраза «три-четыре команды» звучит заманчиво — ведь это противоречиит моим представлениям о некоторых теоретических результатах в этой области. Буду рад узнать, что я ошибался.
Но вообще, конечно, обсуждаются реалзации на языке высокого уровня.
Хм. Ну, возможно, мои измерения были не совсем точны, и второй алгоритм действительно немного быстрее. Может быть, дело в том, что у Вас многоядерный процессор, а у меня одноядерный? Я, если честно, не очень хорошо в этом разбираюсь, но, может быть, это могло как-то повлиять.
Это в принипе, конечно, верно, но, как показывает практика (то бишь, эксперименты), третий алгоритм в среднем даже немного быстрее. Кроме того, не думаю, что на пяти условных переходах можно опрелённо сказать, была ли работа предсказателя положительной или отрицательной — это слишком мало, здесь он не совершает никакой осмысленной работы.
Но если серединное слово ненулевое — то тоже надо продолжать поиск в старшей части. Перейти к младшей можно, только проверив всю старшую половину.
«На всякий случай, поясню: старшим битов называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа.»
Здесь, разумеется, имеется в виду само по себе натуральное число, а не то, сколько места оно занимает в памяти.
Так, ещё раз. В статье шла речь о числах от 1 до 2^31-1. То есть, о тех, у кого единичными могут быть только биты от 0-го до 30-го. В упомянутом Вами числе единственный ненулевой бит — 32-ой. Значит, не будет ни одного бита, который был бы единичным и в х, и в 2^32. Значит, все биты выражения x & (2^32) будут нулевыми. То есть, результат этого выражения будет равен нулю.
Но и Вы правы, да. В зависимости от ситуации, возможно, можно сделать и для двух байтов табличку.
Правда, как уже заметили ruguevara и mephisto, сточки зрения алгоритма — этот, по сути, такой же, как первый.
Да, может быть, особенности языка.
Тогда ваше выражение выдаёт два возможных ответа: 0 или 2^32. Очевидно, что возможных ответов в этой задаче гораздо больше.
& — это побитовое логическое И, не так ли?
Но вообще, конечно, обсуждаются реалзации на языке высокого уровня.
За ссылки спасибо)
Да этим в основном марафонцы занимаются, оптимизированием каждого кусочка кода.