Leodestroy Life Blog
Даже не думал что мне придется столкнуться с чем-то подобным, но как говорится все бывает в первый раз. Дублирую как заметку статью с Хабра для нового проекта по lineage 2.
Побитовые операции пременяются для быстрого выполнения вычислений и меньшего потребления ресурсов, связанных с этими вычислениями.
В Java существуют следующие виды побитовых операций:
| | | ИЛИ (OR) |
| & | И (AND) |
| ^ | ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) |
| ~ | ОТРИЦАНИЕ (NOT) |
Так же стоит выделить операции битового сдвига:
| сдвиг влево | |
| >> | сдвиг вправо |
| >>> | беззнаковый сдвиг вправо |
Побитовые операции
Применяются к каждой паре битов, которые стоят в одинаковых позициях в двух битовых последовательностях.
Оператор обозначается символом |
Выставляет значение в 1, если установлен соответствующий бит в первой или во второй последовательности, или вместе
00000000 00000000 00000000 01111011 (123) | 00000000 00000000 00000001 11001000 (456) = 00000000 00000000 00000001 11111011 (507) Обозначается символом &
Выставляет значение в 1, если установлены соответствующие биты в первой и второй последовательности одновременно
00000000 00000000 00000000 01111011 (123) & 00000000 00000000 00000001 11001000 (456) = 00000000 00000000 00000000 01001000 (57) Обозначается символом ^
Выставляет значение в 1, если установлен соответствующий бит или в первой или во второй во второй последовательности, но не одновременно.
Если используется более двух последовательностей, то в результате будет единица тогда, когда общее количество единиц соответствующей позиции нечетное.
00000000 00000000 00000000 01111011 (123) ^ 00000000 00000000 00000001 11001000 (456) = 00000000 00000000 00000001 10110011 (435) ПОБИТОВОЕ ОТРИЦАНИЕ (NOT)
Обозначается символом ~
Унарный оператор, т.е. применяется к одной последовательности. Превращает каждый бит в противоположный.
~ 00000000 00000000 00000000 01111011 (123) = 11111111 11111111 11111111 10000100 (-124) Знаковый оператор сдвига влево
Все биты смещаются влево. Число справа дополняется нулем. Операция используется для быстрого умножения на 2. Если оператор применяется к числу, умножение на 2 которого будет больше максимального значения int (2147483647), то в результате будет отрицательное число. Это происходит потому, что краний левый бит, который отвечает за знак числа, выставляется в единицу, что соответствует отрицательным числам.
11111111 11111111 11111111 10000101 (-123) 11111111 11111111 11111111 00001010 (-246) Знаковый оператор сдвига вправо >>
Все биты смещаются вправо. Число слева дополняется нулем, если число положительное и единицей, если отрицательное. Операция используется для быстрого деления на 2. Если делится нечетное число, то остаток отбрасывается для положительных чисел и сохраняется для отрицательных.
11111111 11111111 11111111 10000101 (-123) >> 11111111 11111111 11111111 11000010 (-62) Беззнаковый оператор сдвига >>>
Все биты смещаются вправо, число слева дополняется нулем, даже если операция выполняется с отрицательными числами. Отсюда и название оператора — беззнаковый. В результате применения оператора всегда получается положительное число, т.к. в Java левый бит отвечает за знак числа. Операция так же, как и знаковый оператор сдвига вправо, соответствует делению числа на два за исключением первого сдвига в отрицительном числе.
11111111 11111111 11111111 10000101 (-123) >>> 01111111 11111111 11111111 11000010 (2147483586) Применение на практике
Первое, что нам нужно понимать, что за последовательностью битов скрывается какая-то информация, которой мы можем управлять посредством битовых операций, например, это может быть список булевых значений или просто числа, которыми удобнее манипулировать в двоичном представлении
Когда количество сдвигов превышает количество разрядов
При использовании битовых сдвигов важно помнить, что когда количество сдвигов достигает количества разрядов, следующий сдвиг вернет значение в исходное положение. Например, сдвиг влево:
0 - 00000000000000000000000001111011 (123) 1 - 00000000000000000000000011110110 (246) . 30 - 11000000000000000000000000000000 (-1073741824) 31 - 10000000000000000000000000000000 (-2147483648) 32 - 00000000000000000000000001111011 (123) Так же имеет смысл заметить, что после 31-го сдвига нет позиции, где все нули.
Приведение чисел к соответствующему типу данных
При использовании побитовых операций с типами данных byte/short, числа сначала приводятся к типу int, а если одно из чисел — long, то к long.
int i = Integer.MAX_VALUE; //1111111111111111111111111111111 long l = Long.MAX_VALUE; //111111111111111111111111111111111111111111111111111111111111111 long r1 = i&l; long r2 = l&l; //r1 - 000000000000000000000000000000001111111111111111111111111111111 (2147483647) //r2 - 111111111111111111111111111111111111111111111111111111111111111 (9223372036854775807) long l1 = -9223372032559808513L; int i1 = (int) l1; //2147483647 l1 - 1000000000000000000000000000000011111111111111111111111111111111 r1 - 11111111111111111111111111111111 Одним из приемов работы с битовыми данными является использование маски . Маска позволяет получать значения только определенных битов в последовательности. Например, у нас есть маска 00100100, она позволяет нам получать из последовательности только те биты, которые в ней установлены. В данном случае это 3-й и 7-й разряд. Для этого достаточно выполнить побитовое И с нашей маской и неким числом:
01010101 & 00100100 = 00000100 Битовая маска используется, например, при определении маски подсети в сетевой адресации.
Хранение в одной целочисленной переменной нескольких значений
При помощи битовых сдвигов можно хранить в одной целочисленной переменной несколько значений меньшей длины. Например, в первых нескольких битах можно хранить одно число, в следующих битах — другое. Требуется только знать, на сколько бит выполняется сдвиг и сколько бит занимает хранимое число. Для записи используется логическое ИЛИ, для получения — И.
В следующем примере в одном числе сохраняются три значения — возраст, рост, вес, а затем считываются из него. Недостатком такой системы является необходимость помнить, что хранимые значения не должны превышать количество бит, которые определены для них. Например, если в примере одно из значений будет превышать число 255, то мы получим ошибочный результат.
int age, height, weight, combined, mask; age = 28; //00011100 height = 185; //10111001 weight = 80; //01010000 combined = (age) | (height 8) | (weight 16); //00000000 01010000 10111001 00011100 mask = 0b11111111; System.out.printf("Age: %d, height: %d, weight: %d", mask & combined, mask & combined >>> 8, mask & combined >>> 16); //Age: 28, height: 185, weight: 80 Работа с правами доступа
Еще один рапространенный пример применения побитовых операций — работа с правами доступа к папкам и файлам. Принцип следующий. Имеется последовательность из трех битов, где:
001 — первый бит отвечает за права на выполнение
010 — второй — запись
100 — третий — чтение
Имеем следующие константы.
final int EXECUTE = 1; //001 final int WRITE = 2; //010 final int READ = 4; //100 Допустим, нам требуется дать пользователю полный доступ к ресурсу. Для этого должен быть выставлен каждый бит:
int usersAccess = EXECUTE | WRITE | READ; //Получили значение 7 (111) usersAccess = usersAccess ^ EXECUTE //Получили значение 6 (110) Обмен переменных местами без использования временной переменной
Исключающее ИЛИ может быть использовано для обмена двух переменных без создания временной переменной:
Правда, в реальной жизни способ с временной переменной работает быстрее. Данный пример приведен только в познавательных целях.
На основе иключающего ИЛИ работает шифр Вернама , для которого была доказана абсолютная криптографическая стойкость. Шифр был « взломан » в фильме «Пароль «Рыба-меч»»
Быстрое умножение и деление
Операции сдвига рекомендуют использовать для быстрого умножения и деления целых чисел на числа, равные степени двойки. Например, выражение 3
Хранение списка булевых значений и манипуляция ими
Побитовое ИЛИ может быть использовано для установки в 1 необходимых позиций битов в последовательности. Это позволяет, например, хранить список булевых значений в максимально сжатом виде
С помощью исключающего ИЛИ можно переключать заданные биты на противоположные, что позволяет манипулировать набором булевых значений.
Как проверить, является ли число степенью двойки?
С помощью побитовых операций можно за константное время проверить, является ли число степенью двойки:
Данное выражение работает для всех чисел, кроме 0, а 0 не является степенью двойки. Поэтому конечный вариант должен выглядеть так:
Как это работает:
В числе 2 в степени n в единицу выставлен только (n+1)-й бит. Все остальные — нули. Например, числа 16 и 32 имеют двоичный вид, соответственно, 10000 и 100000. Т.е. нам необходимо проверить, что в числе выставлен только один бит.
Допустим, число k — два в степени n. В числе k в единицу выставлен (n+1)-й бит. Тогда в числе k-1 в единицу будут выставлены все биты от 1 до n. Если с такими числами выполнить побитовое И, то в результате должен получиться 0. Например:
32 & 31 == 0 //true 100000 & 011111 = 000000 Вывод
Вывод простой. Программист должен знать побитовые операции и уметь ими пользоваться. Это в некоторых случаях может упростить ему жизнь.
Ну и домашнее задание напоследок. Почему в HashMap в Java для определения индекса используется логическое И?
static int indexFor(int h, int length) < return h & (length-1); > Использованная литература:
Побитовые операции и операции битового сдвига в Java от Unknown (Leodestroy Life Blog) : Даже не думал что мне придется столкнуться с чем-то подобным, но как говорится все бывает в первый раз. Дублирую как заметку статью с Хаб. ‘ onclick=’window.open(this.href + encodeURIComponent(this.title) + «&event=
Даже не думал что мне придется столкнуться с чем-то подобным, но как говорится все бывает в первый раз. Дублирую как заметку статью с Хаб. ‘ onclick=’window.open(this.href + encodeURIComponent(this.title) + «&body=» + encodeURIComponent(this.name), «_blank», «height=560,width=1005»); return false;’ rel=’nofollow’ style=’background: url(«https://lh6.googleusercontent.com/-3gnlQVPOQcQ/TzURgEWMOBI/AAAAAAAAAdA/iGxaDkWX9RA/s25/but7bw.png») no-repeat; font-size:25px;’ title=’Побитовые операции и операции битового сдвига в Java’>
Проверить, является ли число точной степенью двойки
Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.
Операцией возведения в степень пользоваться нельзя!
Входные данные
Вводиться натуральное число.
Выходные данные
Выведите ответ на задачу.
Побитовые операции: проверить, является ли число степенью двойки
Всем добрый день, только начал изучать Java и застрял на одной задаче по побитовым операциям, вот.
Нужно применить быстрое преобразование Фурье к массиву, длина которого не является степенью двойки
Всем добрый день! Столкнулся с проблемой, что нужно применить быстрое преобразование Фурье к.
Функция проверяющая является ли число степенью 5
Описать функцию IsPower5(K) логического типа, возвращающую True, если целый параметр K (> 0).
Если число является степенью числа 3, то вывести True, если не является – вывести False
3.Дано целое число N(>0). Если оно является степенью числа 3, то вывести True, если не является –.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
import java.util.Scanner; public class Starter { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Input num: "); int num = in.nextInt(); while (num != 1 && num % 2 == 0) { num /= 2; } System.out.println(num == 1 ? "YES" : "NO"); } }
Scanner in = new Scanner(System.in); System.out.print("Enter num: "); int n = in.nextInt(); if((n > 0) && ((n & (n - 1)) == 0)) System.out.println("YES"); else System.out.println("NO");