Побитовые операции

@Dosia 77 · Регистрация: 03.10.2018

Студворк — интернет-сервис помощи студентам

Дана задача

Реализуйте метод flipBit, изменяющий значение одного бита заданного целого числа на противоположное. Данная задача актуальна, например, при работе с битовыми полями.

Договоримся, что биты нумеруются от младшего (индекс 1) к старшему (индекс 32).

Есть решение.

Java
1
2
3
public static int flipBit(int value, int bitIndex) {
    return value ^ (1 << bitIndex-1); // put your implementation here
}

Нельзя ли разъяснить подробно решение.
Буду очень признательна, если кто-нибудь объяснит чайнику, как оно так получилось.

@iSmokeJC · 14.10.2018, 14:09

Сообщение от Dosia 77

bitIndex-1

Уменьшаем индекс на 1, т.к. договорились считать с 1, а по феншую - с 0.

Сообщение от Dosia 77

(1 << bitIndex-1)

Сдвигаем влево на n бит, без заполнения, т.е. например
1 << 3 = 8, т.к. 0001 сдвинули влево три раза, получили 1000
Далее используем на полученных числах логическое исключающее ИЛИ, которое в случае, включенного бита одного из операндов "возвращает" 1, а ежели бит включен у обоих операндов - 0. Т.е. инвертирует бит.

Например, используем этот метод со значениями 25 и 3
1 1 0 0 1 (25)
сдвигаем единицу 2 раза (bitIndex-1 = 2)
0 0 1 0 0
----------
1 1 0 0 1
XOR
0 0 1 0 0
=
1 1 1 0 1 (29)

Как-то так...

@OwenGlendower · 14.10.2018, 14:17

Dosia 77, 1) получаем число с 1 (в двоичной записи) в нужной позиции и 0 в остальных битах с помощью оператора сдвига влево (<<). Из bitIndex вычитается 1 т.к. нумерация битов идет с нуля.

2) Меняем нужный бит на противоположный с помощью оператора исключающего ИЛИ не меняя остальные. Для нужного бита работают правила: 0 ⊕ 1 = 1, 1 ⊕ 1 = 0. Для остальных 0 ⊕ 0 = 0, 1 ⊕ 0 = 1.

@Aviz__ · 14.10.2018, 14:37

Сообщение от Dosia 77

как оно так получилось

если хочешь понять, правда хочешь, то берешь листок в клетку, ручку и на 8-и битах - это байт делаешь разные побитовые операции описанные выше. Максиму потратишь час, а профит на всю жизнь.

@Dosia 77 · 14.10.2018, 17:18 **[ТС]**

iSmokeJC,
А как быть вот с этим 42 и 3.

101010 сдвигаем на 2
получаем:
101000

101010
XOR:
101000
=
000010

или я не правильно сдвинула?

@OwenGlendower · 14.10.2018, 17:25

Dosia 77, свигается не само число, а единица.

Code
1
2
3
4
5
6
7
1 << 2 = 100
 
101010
^
000100
=
101110

@Dosia 77 · 14.10.2018, 18:05 **[ТС]**

OwenGlendower,
Я дико извиняюсь за навязчивость. Но мне не удалось нагуглить внятных примеров со сдвигами.

вот мои предидущие выводы
3<<101100 = 100000;
4<< 101110 = 100000;
то бишь, я отбрасываю цифры слева и дописываю нули справа.
Но оказалось, что неверно.
2<<101110; я думала, что получиися
111000.
А как должно?
Вы не могли бы, если есть время написать мне пару разных примеров со сдвигами, как это работает.
Или кинуть ссылку на ресурс, где это объясняют не только на словах, но и на примерах.
Заранее благодарна!))

@Aviz__ · 14.10.2018, 18:09

Сообщение от Dosia 77

не удалось нагуглить

жаль конечно, но это чистая ложь! Пишешь "побитовый сдвиг" в гугол и выбираешь картинки.
https://habr.com/post/279441/

@OwenGlendower · 14.10.2018, 18:13

Сообщение от Dosia 77

я отбрасываю цифры слева и дописываю нули справа.

Правильно. Нужно только не забывать что биты не просто отбрасываются, а только те которые не помещаются в число. То есть важна разрядность (количество битов) нашего типа. И, второе, не забывайте про правильный порядок аргументов. Сначала сдвигаемое число затем на сколько сдвигаем. Запись 3<<101100 означает сдвиг 3 на 44 бита влево. Мы так получим 0 в итоге, если только мы не работаем с типом размерностью больше 32 битов.

@Dosia 77 · 14.10.2018, 18:15 **[ТС]**

Супер! Про картинки мне в голову не пришло!
Я всегда выбирала сайты с многословными объяснениями!
Спасибо Вам:333!

@OwenGlendower · 14.10.2018, 18:15

Сообщение от Aviz__

жаль конечно, но это чистая ложь!

Не торопитесь вешать ярлыки. Не все умеют формулировать правильные поисковые запросы. Особенно новички.

@Aviz__ · 14.10.2018, 18:24

Сообщение от OwenGlendower

вешать ярлыки

даже и не думал, глубокоуважаемый, я лишь усомнился в истинности высказывания ТС. Не мягко, согласен. Но и наш мир не райские кущи...

@Dosia 77 · 14.10.2018, 18:51 **[ТС]**

Мне очень стыдно, но я запуталась ещё больше.
Есили << 2 например - это откинуть слева две цифры, справа добавить нули, то почему тогда
101010 со сдвигом влево на два
= 0001000 , не 101000.
Куда исчезает ещё одна единица?
Если двигать единицу на две позиции влево, то она как бы наслаивается на ту, что там уже есть? Или как. Вот непонятка.

@OwenGlendower · 14.10.2018, 19:17

Dosia 77, 101010 << 2 будет 10101000. Слева ничего в данном случае ничего не выкидывается т.к. в даже в одном байте хватает места. То есть мы только задвинули два нуля справа.

@Dosia 77 · 15.10.2018, 15:59 **[ТС]**

Итак алгоритм (1 << bitIndex -1)
по условию задачи задана переменная int = 32 бита. И 32 знака.
Если двигать влево много раз, циклом for, вылезти за пределы 32 знаков, то получится ноль. Но мне нет необходимости лезть в такие дебри, учитывая, что это не входит в условие задачи.

Допустим, пусть будет четыре знака, для начала.
<<1010 меняем третий знак, значит сдвиг на 2

101000
001010
100010
не изменился

1010 меняем 4 ый знак, значит сдвиг на 3

1010000
0001010
1011010
не изменился

1010 меняем второй знак, значит сдвиг на 1

10100
01010
11110 не изменился, подлец.

и что тут думать?
Я теперь на калькуляторе считала. Что я делаю не так?
Я так и не поняла в чём тут дело.
С другими числами это работает, но не где чередуются единицы-нули 10101010

@OwenGlendower · 15.10.2018, 16:32

Сообщение от Dosia 77

Итак алгоритм (1 << bitIndex -1)

Да. Берется число 00000001₂ и сдвигается влево на значение bitIndex -1. В итоге получится число с одной двоичной единицей.

bitIndex	Результат (двоичная система)	Результат (десятичная система)
1	0000_0001₂	1
2	0000_0010₂	2
3	0000_0100₂	4
4	0000_1000₂	8
5	0001_0000₂	16
6	0010_0000₂	32
7	0100_0000₂	64
8	1000_0000₂	128
9	1 000_0000₂	256
	И так далее

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

@Dosia 77 · 15.10.2018, 17:41 **[ТС]**

Вот ТЕПЕРЬ всё встало на свои места. Аллилуйя!))))
Я могу объяснить Вам, в чём был затык, если Вам действительно интересно.
Это довольно многословно получиться

@OwenGlendower · 15.10.2018, 19:17

Dosia 77, объясните если есть желание

@Dosia 77 · 15.10.2018, 19:38 **[ТС]**

Как Вы уже поняли, я недавно изучаю java.
С побитовыми операциями дело не имела, кроме беглого ознакомления. Эта задача со Stepik. В том виде дана, как я её и скопировала.
Всё у меня упёрлось в синтаксис. Поэтому и просила объяснить, как это работает наглядно.
Во первых я долго думала, что такое value, теперь поняла, что это любое число в двоичном коде.
Опять же сам алгоритм (1<<bitIndex -1) что это и к чему пришить?
теперь до меня дошло, что это любое число с одной единицей из той таблицы, что Вы мне скинули. То бишь загадочный “bitIndex”. А я то думала, что bitIndex это именно количество сдвигов, а не число с одной единичкой и что двигать нужно именно её.
Из вашего первого объяснения я подумала, что надо двигать value и с ним же делать xor с несдвинутым числом
я двигала этих несчастных 42 и делала xor с несдвинутым числом, как Вы и предпологали.
А экспериментально на калькуляторе и вовсе выглядит всё проще пареной репы.
Вопрос, как это записать? Но теперь я знаю ))))
Вот такой тупизм. Конечно, если бы не сразу готовый метод давали, а хоть показали что там и как задаётся, было бы проще.
Спасибо Вам, что столько времени на меня потратили!

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@OwenGlendower Администратор 18261 / 14186 / 5366 Регистрация: 17.03.2014 Сообщений: 28,871 Записей в блоге: 1
	14.10.2018, 14:17
	Dosia 77, 1) получаем число с 1 (в двоичной записи) в нужной позиции и 0 в остальных битах с помощью оператора сдвига влево (<<). Из bitIndex вычитается 1 т.к. нумерация битов идет с нуля. 2) Меняем нужный бит на противоположный с помощью оператора исключающего ИЛИ не меняя остальные. Для нужного бита работают правила: 0 ⊕ 1 = 1, 1 ⊕ 1 = 0. Для остальных 0 ⊕ 0 = 0, 1 ⊕ 0 = 1. 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	14.10.2018, 17:18 [ТС]
	iSmokeJC, А как быть вот с этим 42 и 3. 101010 сдвигаем на 2 получаем: 101000 101010 XOR: 101000 = 000010 или я не правильно сдвинула? 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	14.10.2018, 18:05 [ТС]
	OwenGlendower, Я дико извиняюсь за навязчивость. Но мне не удалось нагуглить внятных примеров со сдвигами. вот мои предидущие выводы 3<<101100 = 100000; 4<< 101110 = 100000; то бишь, я отбрасываю цифры слева и дописываю нули справа. Но оказалось, что неверно. 2<<101110; я думала, что получиися 111000. А как должно? Вы не могли бы, если есть время написать мне пару разных примеров со сдвигами, как это работает. Или кинуть ссылку на ресурс, где это объясняют не только на словах, но и на примерах. Заранее благодарна!)) 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	14.10.2018, 18:15 [ТС]
	Супер! Про картинки мне в голову не пришло! Я всегда выбирала сайты с многословными объяснениями! Спасибо Вам:333! 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	14.10.2018, 18:51 [ТС]
	Мне очень стыдно, но я запуталась ещё больше. Есили << 2 например - это откинуть слева две цифры, справа добавить нули, то почему тогда 101010 со сдвигом влево на два = 0001000 , не 101000. Куда исчезает ещё одна единица? Если двигать единицу на две позиции влево, то она как бы наслаивается на ту, что там уже есть? Или как. Вот непонятка. 0

@OwenGlendower Администратор 18261 / 14186 / 5366 Регистрация: 17.03.2014 Сообщений: 28,871 Записей в блоге: 1
	14.10.2018, 19:17
	Dosia 77, 101010 << 2 будет 10101000. Слева ничего в данном случае ничего не выкидывается т.к. в даже в одном байте хватает места. То есть мы только задвинули два нуля справа. 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	15.10.2018, 15:59 [ТС]
	Итак алгоритм (1 << bitIndex -1) по условию задачи задана переменная int = 32 бита. И 32 знака. Если двигать влево много раз, циклом for, вылезти за пределы 32 знаков, то получится ноль. Но мне нет необходимости лезть в такие дебри, учитывая, что это не входит в условие задачи. Допустим, пусть будет четыре знака, для начала. <<1010 меняем третий знак, значит сдвиг на 2 101000 001010 100010 не изменился 1010 меняем 4 ый знак, значит сдвиг на 3 1010000 0001010 1011010 не изменился 1010 меняем второй знак, значит сдвиг на 1 10100 01010 11110 не изменился, подлец. и что тут думать? Я теперь на калькуляторе считала. Что я делаю не так? Я так и не поняла в чём тут дело. С другими числами это работает, но не где чередуются единицы-нули 10101010 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	15.10.2018, 17:41 [ТС]
	Вот ТЕПЕРЬ всё встало на свои места. Аллилуйя!)))) Я могу объяснить Вам, в чём был затык, если Вам действительно интересно. Это довольно многословно получиться 0

@OwenGlendower Администратор 18261 / 14186 / 5366 Регистрация: 17.03.2014 Сообщений: 28,871 Записей в блоге: 1
	15.10.2018, 19:17
	Dosia 77, объясните если есть желание 0

@Dosia 77 0 / 0 / 0 Регистрация: 03.10.2018 Сообщений: 19
	15.10.2018, 19:38 [ТС]
	Как Вы уже поняли, я недавно изучаю java. С побитовыми операциями дело не имела, кроме беглого ознакомления. Эта задача со Stepik. В том виде дана, как я её и скопировала. Всё у меня упёрлось в синтаксис. Поэтому и просила объяснить, как это работает наглядно. Во первых я долго думала, что такое value, теперь поняла, что это любое число в двоичном коде. Опять же сам алгоритм (1<<bitIndex -1) что это и к чему пришить? теперь до меня дошло, что это любое число с одной единицей из той таблицы, что Вы мне скинули. То бишь загадочный “bitIndex”. А я то думала, что bitIndex это именно количество сдвигов, а не число с одной единичкой и что двигать нужно именно её. Из вашего первого объяснения я подумала, что надо двигать value и с ним же делать xor с несдвинутым числом я двигала этих несчастных 42 и делала xor с несдвинутым числом, как Вы и предпологали. А экспериментально на калькуляторе и вовсе выглядит всё проще пареной репы. Вопрос, как это записать? Но теперь я знаю )))) Вот такой тупизм. Конечно, если бы не сразу готовый метод давали, а хоть показали что там и как задаётся, было бы проще. Спасибо Вам, что столько времени на меня потратили! 0

Побитовые операции

Решение