Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Битовые сдвиги. / 23 сообщений из 23, страница 1 из 1
23.01.2014, 09:05
    #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:07
    #38535168
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Битовые сдвиги.
Тема видимо названа некорректно, к сожалению не знаю как изменить название. Первоначально меня интересовал второй вопрос больше, потому назвал тему исходя из содержания второго вопроса
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2014, 09:50
    #38535195
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Битовые сдвиги.
a&=(a-1); сбрасывает в ноль младший двоичный разряд равный 1.

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

"сбрасывает в ноль младший двоичный разряд равный 1. " почему он сбрасывается ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2014, 10:00
    #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:14
    #38535227
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Битовые сдвиги.
Dima T,
"-1 приводит к инвертированию всех разрядов начиная с младшего до первого равного 1 (включительно)",

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

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

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

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

00010100
-
00000001
00010011
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2014, 10:47
    #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
| Ответить | Цитировать | Написать  
27.01.2014, 02:43
    #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, 05:10
    #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, 08:43
    #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, 09:18
    #38538603
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Битовые сдвиги.
Dima T ,

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

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

Dima T, Anatoly Moskovsky спасибо C:
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.01.2014, 09:19
    #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, 15:50
    #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, 16:32
    #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, 17:05
    #38539379
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Битовые сдвиги.
Dimitry SibiryakovА оно проводится с учётом знаковости или без него?
Т.к короткий тип всегда помещается в знаковый int, то расширенный тип будет знаковым.

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

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

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

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

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

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


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