Побитовые операции - о каких из них полезно знать программистам "более высоких" уровней?
1,00
р.
Здравствуйте!
Задаю этот вопрос скорее для самообразования, чем из реальной сиюминутной необходимости:
Что нужно знать программистам "более высоких уровней" о побитовых операциях? О каких конкретных случаях их применения желательно знать в любом случае? Приведите примеры из вашей практики, когда использования побитовых операций существенно ускоряло/упрощало?/улучшало ваш код?
Что я уже знаю:
Я знаю о битовых масках. знаю, что "x & 1" проверяет чётность числа (например, здесь, ответ @avp) знаю про побитовые сдвиги и умножение/деление на степени двойки.
Также я прочитал все топики на эту тему здесь на ХэшКоде и основные на StackOverflow, нашёл вот этот интересный ресурс: Bit Twiddling Hacks.
Также я наслышан об удивительном решении задачи нахождения Fast inverse square root.
И наслышан о книге Hacker's Delight, которую пока что не читал. Она же на русском.
В дополнение к вопросу напишу, что кроме битовых масок (которые я уже давно использую) из всего того, что мне встретилось, единственным более-менее полезным для себя и своей повседневной практики я нашёл лишь только проверку числа на чётность, что навело меня на мысль, что наверняка должны быть какие-то ещё диковинные случаи, когда использование битовых операций уместно и даже желательно.
И ещё напишу, что интересуюсь этим вопросом сугубо с практической стороны, поэтому скорее буду признателен за простые примеры и реальный опыт, чем за сухие ссылки на "6 том всемирного собрания алгоритмов из какого-нибудь Великого британского учебного учреждения" и всё в таком духе.
Спасибо))
Перечень интересных ссылок на смежные темы
Получение модуля числа без операции сравнения
Do bitwise operators (other than shifts) make any mathematical sense in base-10?
Ответ
Самая главная (для меня естественно) битовая операция это XOR - исключающее или. Операция XOR замечательна тем, что применения 2 раза к одному и тому же битовому массиву восстанавливает ее исходное значени именно это ее свойство активно применяется в операциях шифрования:
C = A xor B //кодирование с помощью вектора B A = C xor B //восстановление исходного значения
Более подробно здесь
Вторая по значимости (опять таки для меня) операция AND - часто применяется для "выцепления" из длинной битовой последовательности конкретной части. Ну например есть long, который надо расщепить на два int'а. Другой пример: есть длинная битовая последовательность, которую скажем, возвращает какой-нить дурацкий контроллер не менее дурацкого устройства, в мануале сказано, что 3-й бит показывает готовность устройства. Берем битовую маску где в 3-й позиции забита единичка (4), а все остальное 0, накладываем на битовый массив и проверяем > 0:
if( (bitsFromController & 4) > 0) //ready!
Ну про битовые сдвижки вы уже сами все написали, так что повторяться не буду.
А OR это просто сложение двух битовых массивов.
Update
Примерчик c битами конвертация байта в 16-тиричную строку (Java):
/* по сути надо входной байт разделить на два 4-х битовых элемента */ public String byteToHex(byte b) { //допустим конвертим 76=01001100 final String HEX="0123456789ABCDEF" char[] val=new char[2] val[0]=HEX.charAt(b >>> 4) //убиваем 4 младших бита получаем 4=0100 val[1]=HEX.charAt(b & 15) // накладываем маску (15=00001111) на 4 младших бита получаем 12=1100 return String.valueOf(val) //возвращаем 4C=76 }
Задаю этот вопрос скорее для самообразования, чем из реальной сиюминутной необходимости:
Что нужно знать программистам "более высоких уровней" о побитовых операциях? О каких конкретных случаях их применения желательно знать в любом случае? Приведите примеры из вашей практики, когда использования побитовых операций существенно ускоряло/упрощало?/улучшало ваш код?
Что я уже знаю:
Я знаю о битовых масках. знаю, что "x & 1" проверяет чётность числа (например, здесь, ответ @avp) знаю про побитовые сдвиги и умножение/деление на степени двойки.
Также я прочитал все топики на эту тему здесь на ХэшКоде и основные на StackOverflow, нашёл вот этот интересный ресурс: Bit Twiddling Hacks.
Также я наслышан об удивительном решении задачи нахождения Fast inverse square root.
И наслышан о книге Hacker's Delight, которую пока что не читал. Она же на русском.
В дополнение к вопросу напишу, что кроме битовых масок (которые я уже давно использую) из всего того, что мне встретилось, единственным более-менее полезным для себя и своей повседневной практики я нашёл лишь только проверку числа на чётность, что навело меня на мысль, что наверняка должны быть какие-то ещё диковинные случаи, когда использование битовых операций уместно и даже желательно.
И ещё напишу, что интересуюсь этим вопросом сугубо с практической стороны, поэтому скорее буду признателен за простые примеры и реальный опыт, чем за сухие ссылки на "6 том всемирного собрания алгоритмов из какого-нибудь Великого британского учебного учреждения" и всё в таком духе.
Спасибо))
Перечень интересных ссылок на смежные темы
Получение модуля числа без операции сравнения
Do bitwise operators (other than shifts) make any mathematical sense in base-10?
Ответ
Самая главная (для меня естественно) битовая операция это XOR - исключающее или. Операция XOR замечательна тем, что применения 2 раза к одному и тому же битовому массиву восстанавливает ее исходное значени именно это ее свойство активно применяется в операциях шифрования:
C = A xor B //кодирование с помощью вектора B A = C xor B //восстановление исходного значения
Более подробно здесь
Вторая по значимости (опять таки для меня) операция AND - часто применяется для "выцепления" из длинной битовой последовательности конкретной части. Ну например есть long, который надо расщепить на два int'а. Другой пример: есть длинная битовая последовательность, которую скажем, возвращает какой-нить дурацкий контроллер не менее дурацкого устройства, в мануале сказано, что 3-й бит показывает готовность устройства. Берем битовую маску где в 3-й позиции забита единичка (4), а все остальное 0, накладываем на битовый массив и проверяем > 0:
if( (bitsFromController & 4) > 0) //ready!
Ну про битовые сдвижки вы уже сами все написали, так что повторяться не буду.
А OR это просто сложение двух битовых массивов.
Update
Примерчик c битами конвертация байта в 16-тиричную строку (Java):
/* по сути надо входной байт разделить на два 4-х битовых элемента */ public String byteToHex(byte b) { //допустим конвертим 76=01001100 final String HEX="0123456789ABCDEF" char[] val=new char[2] val[0]=HEX.charAt(b >>> 4) //убиваем 4 младших бита получаем 4=0100 val[1]=HEX.charAt(b & 15) // накладываем маску (15=00001111) на 4 младших бита получаем 12=1100 return String.valueOf(val) //возвращаем 4C=76 }
