ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Битовые сдвиги.
23 сообщений из 23, страница 1 из 1
Битовые сдвиги.
    #38535165
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте.
1. Я разбирал функцию возвращающую количество единиц в двоичном представлении целого числа int:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
int count (int a)
{
int r=0;
while(a)
{
a&=(a-1);
++r;
}
return r;
}



Эта функция работает, и я понимаю каждую строчку в этом коде, но мне непонятно почему она работает ? То есть я не понимаю почему такой алгоритм ? Например, в функции возвращающей третий угол треугольника в евклидовой геометрии float angle(float an1,float an2) {return 180-an1-an2;} я понимаю всё, и код, и откуда цифра 180, а в функции count я понимаю код, но не понимаю почему. Объясните пожалуйста.

2. Прокомментируйте пожалуйста следующее предложение, оно взято по следующей ссылке http://msdn.microsoft.com/ru-ru/library/vstudio/8xftzc7e(v=vs.100).aspx
" Чтобы при каждом сдвиге оставался хотя бы один исходный бит, операторы сдвига используют следующую формулу для вычисления фактической величины сдвига: маска выражения expression2 (использующая побитовый оператор И) с числом, на единицу меньшим, чем количество битов в выражении expression1. "

Спасибо
...
Рейтинг: 0 / 0
23.01.2014, 09:05
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535168
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Тема видимо названа некорректно, к сожалению не знаю как изменить название. Первоначально меня интересовал второй вопрос больше, потому назвал тему исходя из содержания второго вопроса
...
Рейтинг: 0 / 0
23.01.2014, 09:07
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535195
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
a&=(a-1); сбрасывает в ноль младший двоичный разряд равный 1.

Выводи двоичное значение "а" при каждой итерации цикла. Увидишь как меняется, поймешь.
...
Рейтинг: 0 / 0
23.01.2014, 09:50
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535200
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima T, спасибо за ответ.
Я понимаю каждую строчку этого кода, и понимаю как что меняется. Без вывода на экран, и без рисования на листке. Мне непонятно доказательство данного алгоритма, скажем так обоснование данного метода, если говорить математическим языком

"сбрасывает в ноль младший двоичный разряд равный 1. " почему он сбрасывается ?
...
Рейтинг: 0 / 0
23.01.2014, 09:54
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535206
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury"сбрасывает в ноль младший двоичный разряд равный 1. " почему он сбрасывается ?
-1 приводит к инвертированию всех разрядов начиная с младшего до первого равного 1 (включительно), а 1&0 = 0&1 = 0
Например a=20 или 10100 в двоичном виде (а-1) = 19 = 10011
дальше побитовое И: 10100 & 10011 = 10000
...
Рейтинг: 0 / 0
23.01.2014, 10:00
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535227
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima T,
"-1 приводит к инвертированию всех разрядов начиная с младшего до первого равного 1 (включительно)",

почему такое происходит ?
...
Рейтинг: 0 / 0
23.01.2014, 10:14
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535230
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Или по другому: вспомни школьное правило вычитания столбиком. Возьми ручку, бумагу и проделай тоже самое только в двоичном виде (X-1). Пока в текущем разряде ноль из следующего старшего разряда будет заниматься единица до тех пор пока в старшем разряде не окажется единицы, эта единица станет нулем и на более старшие разряды никак не повлияет.
...
Рейтинг: 0 / 0
23.01.2014, 10:16
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535233
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Понял ))) Минус один, значит число на 1 бит меньше, при вычитании видимо эта инверсия до первой единицы включительно и происходит )
...
Рейтинг: 0 / 0
23.01.2014, 10:19
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535241
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
"Или по другому: вспомни школьное правило вычитания столбиком. Возьми ручку, бумагу и проделай тоже самое только в двоичном виде (X-1). Пока в текущем разряде ноль из следующего старшего разряда будет заниматься единица до тех пор пока в старшем разряде не окажется единицы, эта единица станет нулем и на более старшие разряды никак не повлияет. "

Дада, спасибо ))Я предыдущий комментарий написал когда ещё не видел, всё логично !)

Спасибо, Dima T, первую часть вопроса я определённо понял! Так приятно теперь понимать почему это работает так !
...
Рейтинг: 0 / 0
23.01.2014, 10:22
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535249
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryПонял ))) Минус один, значит число на 1 бит меньше, при вычитании видимо эта инверсия до первой единицы включительно и происходит )
Минус один, значит на один меньше )))

Двоичная арифметика
...
Рейтинг: 0 / 0
23.01.2014, 10:26
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535262
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
я имел ввиду что минус один значит f e:
00010100 вычесть 00000001 , под 00000001 я имел ввиду один бит, обозвал неправильно. Я понял !

00010100
-
00000001
00010011
...
Рейтинг: 0 / 0
23.01.2014, 10:35
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38535279
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury2. Прокомментируйте пожалуйста следующее предложение, оно взято по следующей ссылке http://msdn.microsoft.com/ru-ru/library/vstudio/8xftzc7e(v=vs.100).aspx
" Чтобы при каждом сдвиге оставался хотя бы один исходный бит, операторы сдвига используют следующую формулу для вычисления фактической величины сдвига: маска выражения expression2 (использующая побитовый оператор И) с числом, на единицу меньшим, чем количество битов в выражении expression1. "

Это про битовый сдвиг переменной X на N разрядов при N больше или равно чем всего разрядов в X. По идее всегда должно получаться 0.
Например размер X 1 байт, т.е. 8 бит, сдвинув на 10 исходное значение уйдет за пределы переменной.

ХЗ зачем решили усовершенствовать данную ситуацию, но в данном примере сдвиг будет на 2 разряда 10 & (8-1) или в двоичном виде 1010 & 0111 = 0010. Как предположение: возможно процессор так работает, тупо игнорирует лишнее в N, берет три младших бита из N для сдвига в одном байте.
...
Рейтинг: 0 / 0
23.01.2014, 10:47
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38538570
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima T, спасибо.

В целом, я понял что происходит, но не понял почему. Мне кажется что это используется для вычисления чего-либо. То есть исходя из логики, зачем сдвигать на 10 бит, если размер типа данных 8 бит, очевидно что будет 0, вот и придумали сдвиг.

Кстати. если 10, то получим 2. А если например 24, то тогда:
00011000
&00000111
00000000
Получили 0

А если 13, предполагаю что получим 5

00001101
&00000111
00000101
Получили 5.


То есть фактически происходит операция деление по модулю с размером в битах типа данных.

Всё-же очень интересно где это используется, не случайно это так
...
Рейтинг: 0 / 0
27.01.2014, 02:43
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38538579
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima TХЗ зачем решили усовершенствовать данную ситуацию, но в данном примере сдвиг будет на 2 разряда 10 & (8-1) или в двоичном виде 1010 & 0111 = 0010. Как предположение: возможно процессор так работает, тупо игнорирует лишнее в N, берет три младших бита из N для сдвига в одном байте.
Эта самодеятельность полностью соответствует стандарту.

С++03 / 5.8 Shift operatorsThe behavior is undefined if the right operand is negative, or
greater than or equal to the length in bits of the promoted left operand
Т.е. какой результат будет если сдвиг больше битовой ширины типа - неопределено.
Это может быть как 0 так и вообще случайное число.
Так что, на вот это наложение маски которое делает VS полагаться не стоит, т.к. стандарт не определяет каким должен быть результат в этом случае, и в другом компиляторе может быть по другому.

Обратите внимание также на подчеркнутое (promoted).

Для операций над короткими типам, меньшими чем int (char, short, bool) проводится расширение разрядности (integral promotion) до размера int.

И максимальный размер сдвига, для которого результат гарантирован стандартом, определяется размером int, а не размером конкретного короткого типа.
Поэтому, к примеру, 8-битный char можно сдвигать вплоть до 31 (для x86). При этом для сдвига начиная с 8 и до 31 результат будет гарантированно 0, а больший сдвиг - неопределен.
...
Рейтинг: 0 / 0
27.01.2014, 05:10
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38538594
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury... оно взято по следующей ссылке http://msdn.microsoft.com/ru-ru/library/vstudio/8xftzc7e(v=vs.100).aspx
Присмотрелся, по ссылке про "Операторы (Visual Studio — JScript)", в Си по другому. Как Анатолий написал.
 
Пример из ссылки на Си
Код: plaintext
1.
2.
3.
unsigned char a = 15;
a = a << 10;
printf("%d\n", a); // выдает 0


 
Если посмотреть во что компилируется, то видно что компилятор MSVC все отдает на усмотрение процессора
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
109:      unsigned char a = 15;
0040162E   mov         byte ptr [ebp-4],0Fh
110:      a = a << 10;
00401632   mov         eax,dword ptr [ebp-4]
00401635   and         eax,0FFh
0040163A   shl         eax,0Ah
0040163D   mov         byte ptr [ebp-4],al
111:      printf("%d\n", a);


Сам сдвиг выполняется в процессоре в 32-битном регистре eax командой shl.
SashaMercuryТо есть исходя из логики, зачем сдвигать на 10 бит, если размер типа данных 8 бит, очевидно что будет 0, вот и придумали сдвиг.
Сдвигать 8 бит на 10 незачем, но программы пишут люди и может оказаться что такая ситуация возникнет :)
SashaMercuryВсё-же очень интересно где это используется, не случайно это так
X << N равносильно X * (2 ^ N)
только технически (внутри процессора) гораздо быстрее сдвинуть биты чем умножать и в степень возводить.

Используется для работы с битовыми структурами, например у надо в байте хранить два значения A и B, где A старшие 3 бита, B младшие 5. Тогда конечный байт будет
С = (A << 5) | B или тоже самое A*2^5 + B
и обратное преобразование
A = C >> 5 = округлить вниз до целого (C / (2^5))
B = C & 31 = остаток от деления С на 2^5 (31 это 2^5 - 1 или в двоичной 11111)

По большому счету все битовые операции нужны для учета специфики работы процессора, он двоичный и работает только с двоичными числами и с битами. Если интересно как выполняется программа процессором - изучай ассемблер.
...
Рейтинг: 0 / 0
27.01.2014, 08:43
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38538603
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima T ,

"Всё-же очень интересно где это используется, не случайно это так"
Этот комментарий был не к смыслу в использование побитовых операций, и сдвигов в частности, это мне понятно. Вопрос был, к той специфической операции в VS, согласно которой при сдвиге на размер больший размеру типа данных, сдвиг происходит на остаток от деления на размер типа данных (накладывается маска на размер сдвига).

Но, так как Anatoly Moskovsky указал что в данном случае это только такая работа в VS, и другой компилятор вероятно по другому обработает данную операцию, этот вопрос интересен уже менее.

Dima T, Anatoly Moskovsky спасибо C:
...
Рейтинг: 0 / 0
27.01.2014, 09:18
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38538605
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
"Т.е. какой результат будет если сдвиг больше битовой ширины типа - неопределено.
Это может быть как 0 так и вообще случайное число.
Так что, на вот это наложение маски которое делает VS полагаться не стоит, т.к. стандарт не определяет каким должен быть результат в этом случае, и в другом компиляторе может быть по другому.

Обратите внимание также на подчеркнутое (promoted).

Для операций над короткими типам, меньшими чем int (char, short, bool) проводится расширение разрядности (integral promotion) до размера int.

И максимальный размер сдвига, для которого результат гарантирован стандартом, определяется размером int, а не размером конкретного короткого типа.
Поэтому, к примеру, 8-битный char можно сдвигать вплоть до 31 (для x86). При этом для сдвига начиная с 8 и до 31 результат будет гарантированно 0, а больший сдвиг - неопределен. "

Ну очень здоровский комментарий
...
Рейтинг: 0 / 0
27.01.2014, 09:19
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38539200
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Anatoly MoskovskyДля операций над короткими типам, меньшими чем int (char, short,
bool) проводится расширение разрядности (integral promotion) до размера int.
А оно проводится с учётом знаковости или без него?

Чисто для информации: в процессоре сдвиги вправо бывают четырёх типов:
1) Арифметический: старший бит расширяется.
2) Циклический: в старший бит заносится значение младшего бита
3) С переносом: в старший бит заносится значение флага переноса
4) "Тупой": в старший бит заносится 0.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.01.2014, 15:50
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38539314
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovА оно проводится с учётом знаковости или без него?

Компилятор ставит ассемблерную команду SHL, т.е. "тупой беззнаковый" как я понимаю.

Вот откуда ноги растут Intel Architecture Software Developer’s Manual
стр. 15 (или 3-624)SAL/SAR/ SHL /SHR—Shift (Continued)
Intel Architecture Compatibility
The 8086 does not mask the shift count. However, all other Intel Architecture processors
(starting with the Intel 286 processor) do mask the shift count to five bits, resulting in a
maximum count of 31. This masking is done in all operating modes (including the virtual-8086
mode) to reduce the maximum execution time of the instructions
Как я и предполагал выше: Intel так процы соптимизировал.
...
Рейтинг: 0 / 0
27.01.2014, 16:32
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38539379
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dimitry SibiryakovА оно проводится с учётом знаковости или без него?
Т.к короткий тип всегда помещается в знаковый int, то расширенный тип будет знаковым.

Касательно самих сдвигов - для положительных значений (независимо от того знаковый тип или нет) выполняется простой сдвиг с заполнением нулем.
А для отрицательных значений, операция не описана стандартом и зависит от реализации.

Насколько я знаю, на платформе x86 для знаковых (как положительных так и отрицательных) чисел выполняется арифметический сдвиг (с расширением старшего бита). А для беззнаковых - простой сдвиг. Вышеприведенные требования стандарта при этом обеспечиваются автоматически.
...
Рейтинг: 0 / 0
27.01.2014, 17:05
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38539386
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Anatoly MoskovskyТ.к короткий тип всегда помещается в знаковый int
Ну, тут не всегда конечно, но на практике всегда :)
...
Рейтинг: 0 / 0
27.01.2014, 17:08
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38539522
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryДля операций над короткими типам, меньшими чем int (char, short, bool) проводится расширение разрядности (integral promotion) до размера int.

И максимальный размер сдвига, для которого результат гарантирован стандартом, определяется размером int, а не размером конкретного короткого типа.
Поэтому, к примеру, 8-битный char можно сдвигать вплоть до 31 (для x86). При этом для сдвига начиная с 8 и до 31 результат будет гарантированно 0, а больший сдвиг - неопределен. "

Ну очень здоровский комментарий
Почитай книгу Генри Уоррена - Алгоритмические трюки для программистов.

Там описаны почти все фокусы с битами и численные методы на этих свойствах.

Книга написана так что дефектов плавающей разрядности int нету или по крайней
мере я с ними не сталкивался.
...
Рейтинг: 0 / 0
27.01.2014, 17:58
| Ответить | Цитировать | Написать  
Битовые сдвиги.
    #38539892
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
mayton,
почитаю :) Скачаю сегодня.
Спасибо за совет C:
...
Рейтинг: 0 / 0
28.01.2014, 05:06
| Ответить | Цитировать | Написать  
23 сообщений из 23, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Битовые сдвиги.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]