Вопрос о побитовых логических операциях: теория

Изучаю лекцию по программированию и возникло не понимание описанной в лекции побитовых логических операций.

Вот текст лекции:

Лекция написал:

Побитовые логические операции

В языке предусмотрен ряд операций для работы с битами; эти операции нельзя применять к переменным типа float или double.
Таблица 2.2. & Побитовое AND
| Побитовое включающее OR
^ побитовое исключающее OR
<< сдвиг влево
>> сдвиг вправо
^ дополнение (унарная операция)

"\" имитирует вертикальную черту.

Побитовая операция and часто используется для маскирования некоторого множества битов; например, оператор

c = n & 0177

передает в 'с' семь младших битов n, полагая остальные равными нулю. Операция '|' побитового or используется для включения битов:

c = x | mask

устанавливает на единицу те биты в х, которые равны единице в mask.

Следует быть внимательным и отличать побитовые операции & и | от логических связок && и ||, которые подразумевают вычисление значения истинности слева направо. Например, если х=1, а y=2, то значение х&y равно нулю, в то время как значение x&&y равно единице.

Операции сдвига << и >> осуществляют соответственно сдвиг влево и вправо своего левого операнда на число битовых позиций, задаваемых правым операндом. Таким образом, х<<2 сдвигает х влево на две позиции, заполняя освобождающиеся биты нулями, что эквивалентно умножению на 4. Сдвиг вправо величины без знака заполняет освобождающиеся биты на некоторых машинах, таких как PDP-11, заполняются содержанием знакового бита "арифметический сдвиг", а на других - нулем "логический сдвиг".

Унарная операция ^ дает дополнение к целому; это означает, что каждый бит со значением 1 получает значение 0 и наоборот. Эта операция обычно оказывается полезной в выражениях типа

x & ^077

где последние шесть битов х маскируются нулем. Подчеркнем, что выражение x&^077 не зависит от длины слова и поэтому предпочтительнее, чем, например, x&0177700, где предполагается, что х занимает 16 битов. Такая переносимая форма не требует никаких дополнительных затрат, поскольку ^077 является константным выражением и, следовательно, обрабатывается во время компиляции.

Чтобы проиллюстрировать использование некоторых операций с битами, рассмотрим функцию getbits(x,p,n), которая возвращает /сдвинутыми к правому краю/ начинающиеся с позиции р поле переменной х длиной n битов. Мы предполагаем, что крайний правый бит имеет номер 0, и что n и р - разумно заданные положительные числа. Например, getbits(х,4,3) возвращает сдвинутыми к правому краю биты, занимающие позиции 4,3 и 2.

getbits(x,p,n) /* get n bits from position p */
unsigned x, p, n;
{
return((x >> (p+1-n)) & ^(^0 << n));
}

Операция x >> (p+1-n) сдвигает желаемое поле в правый конец слова. описание аргумента x как unsigned гарантирует, что при сдвиге вправо освобождающиеся биты будут заполняться нулями, а не содержимым знакового бита, независимо от того, на какой машине пропускается программа. Все биты константного выражения ^0 равны 1; сдвиг его на n позиций влево с помощью операции ^0<<n создает маску с нулями в n крайних правых битах и единицами в остальных; дополнение ^ создает маску с единицами в n крайних правых битах.

Простите, но мне не понятно фраза:


1) c = n & 0177 передает в 'с' семь младших битов n, полагая остальные равными нулю.

2)c = x | mask устанавливает на единицу те биты в х, которые равны единице в mask.

Мне не понятен смысл этих двух фраз. Кто может объясните, пожалуйста.

hardorsoft написал:

1) c = n & 0177 передает в 'с' семь младших битов n, полагая остальные равными нулю.

N = abcd efghi jklm nopq (2) // a-q - произвольные двоичные цифры
C -> abcd efghi jklm nopq & 0000 0000 0111 1111 -> 0000 0000 0klm nopq

hardorsoft написал:

2)c = x | mask устанавливает на единицу те биты в х, которые равны единице в mask.

X = abcd efghi jklm nopq (2)
mask = 0000 0000 0111 1111
C -> abcd efghi j111 1111

Спасибо, теперь кажется понятно,
таким образом получается что мы сравниваем не значения переменных,
а образно говоря "ячейки памяти" в которых находятся какие-то значения.

мы производим операцию (и/или) над каждым битом операндов

Тем не менее еще один вопрос.
Что делает следующая функция?

getbits(x,p,n) /* get n bits from position p */
unsigned x, p, n;
{
return((x >> (p+1-n)) & ^(^0 << n));
}

она выдаёт ошибку компиляции.... там наверное тильда(~), а не крышечка(^)

стоп... а что это за язык?

и комментарий ни на что не намекает?

Возможно, но тогда в лекции ошибка.
А про тильду в лекции ничего не сказано.

Как понять следующее:

getbits(x,p,n) /* get n bits from position p */
unsigned x, p, n;
{
return((x >> (p+1-n)) & ^(^0 << n));
}

Операция x >> (p+1-n) сдвигает желаемое поле в правый конец слова. описание аргумента x как unsigned гарантирует, что при сдвиге вправо освобождающиеся биты будут заполняться нулями, а не содержимым знакового бита, независимо от того, на какой машине пропускается программа. Все биты константного выражения ^0 равны 1; сдвиг его на n позиций влево с помощью операции ^0<<n создает маску с нулями в n крайних правых битах и единицами в остальных; дополнение ^ создает маску с единицами в n крайних правых битах.

Если верить лекции, то (^0<<n) должна сначала заполнить последние n битов единицами, а ^(^0<<n) должна эти n битов заменить нулями.

Язык Си. Впервые сталкиваюсь с битовыми операциями, поэтому мне сложно разобраться.

Чтобы проиллюстрировать использование некоторых операций с битами, рассмотрим функцию getbits(x,p,n), которая возвращает /сдвинутыми к правому краю/ начинающиеся с позиции р поле переменной х длиной n битов. Мы предполагаем, что крайний правый бит имеет номер 0, и что n и р - разумно заданные положительные числа. Например, getbits(х,4,3) возвращает сдвинутыми к правому краю биты, занимающие позиции 4,3 и 2.

getbits(x,p,n) /* get n bits from position p */
unsigned x, p, n;
{
return((x >> (p+1-n)) & ^(^0 << n));
}

Операция x >> (p+1-n) сдвигает желаемое поле в правый конец слова. описание аргумента x как unsigned гарантирует, что при сдвиге вправо освобождающиеся биты будут заполняться нулями, а не содержимым знакового бита, независимо от того, на какой машине пропускается программа. Все биты константного выражения ^0 равны 1; сдвиг его на n позиций влево с помощью операции ^0<<n создает маску с нулями в n крайних правых битах и единицами в остальных; дополнение ^ создает маску с единицами в n крайних правых битах.

Как я понимаю функция getbits(x,4,3) если х = 'abcdefgh', должна вернуть 'efg'?
Или 'bcd'?
Самому у меня не получается разобраться.

Поскольку

Мы предполагаем, что крайний правый бит имеет номер 0

p+1-n   = 4+1-3   = 2 (dec)
x                 = 00000000 00000000 00000000 abcdefgh (bin)
x >> 2            = 00000000 00000000 00000000 00abcdef (bin)
0                 = 00000000 00000000 00000000 00000000 (bin)
~0                = 11111111 11111111 11111111 11111111 (bin)
~0 << n = ~0 << 3 = 11111111 11111111 11111111 11111000 (bin)
~(~0 << n)        = 00000000 00000000 00000000 00000111 (bin)
(x >> 2) & ~(~0 << n) =
  00000000 00000000 00000000 00abcdef (bin)
& 00000000 00000000 00000000 00000111 (bin)
 -------------------------------------------
  00000000 00000000 00000000 00000def (bin)

не знаю, что это, но на си это будет выглядеть так:

unsigned getbits(unsigned x, unsigned p, unsigned n)  /* get n bits from position p */
{
    return ((x >> (p+1-n)) & ~(~0 << n));
}

остальное то что написано - разумно

ок сейчас попробую.

Fat-Zer написал:

не знаю, что это, но на си ...

Это K&R (Kernighan and Ritchie) синтаксис описания функций в C, если эти имена что-то вам говорят wink

hardorsoft написал:

Вот текст лекции:
[quote=Лекция]Побитовые логические операции
^ побитовое исключающее OR
^ дополнение (унарная операция)

Все что вы объясняется вроде ясно, но вот пробую прогнать функцию на компе... Что-то не так работает.

#include <stdio.h>

main()
{
unsigned x;
x = getbits("abcdefgh", 4, 3);
printf("%u***\n", x);

}
getbits(x,p,n) /* get n bits from position p */
unsigned x, p, n;
{

return ((x >> (p+1-n)) & ~(~0 << n));
}

[console]
./temp
0***
[/console]

Что-то не так?

getbits("abcdefgh", 4, 3)

Первым параметром getbits является беззнаковое целое (unsigned int), например, getbits(31, 4, 3).
Результатом является знаковое целое (хотя логичнее было бы тоже беззнаковое).

Почему компилятор не ругается на getbits("abcdefgh", 4, 3) ? Строковый литерал -- это указатель (char *), который на 32-разрядной платформе безболезненно (с предупреждением?) преобразуется к (unsigned int), функция получает адрес переданной строки и использует его, а не строку, как (unsigned int).

#include <stdio.h>

main()
{
unsigned x;
x = getbits(31, 4, 3);
printf("%u***\n", x);

}

getbits(x,p,n) /* get n bits from position p */
unsigned x, p, n;
{
//unsigned c;
return ((x >> (p+1-n)) & ~(~0 << n));
//printf("%u\n", x);
}

[console]
./temp
7***
[/console]
Простите вообще это правильный вывод?

Проверьте "на карандаше":

31(dec) = 1f(hex)   = 11111(bin)
позиции бит:          43210
выделяем с 4, 3 бита: ^^^
получаем              111(bin) = 7(dec)

getbits(23, 4, 3) = 101(bin) = 5(dec)

23(dec) = 17(hex)   = 10111(bin)
позиции бит:          43210
выделяем с 4, 3 бита: ^^^

Спасибо за ответы.
Следующая задача по этой же теме:

Переделайте getbits таким образом, чтобы биты отсчитывались слева направо.

    // Функция которую нужно переделать.
    #include <stdio.h>
    main()
    {
    unsigned x;
    x = getbits(31, 4, 3);
    printf("%u***\n", x);
    }
    getbits(x,p,n)  /* get n bits from position p */
    unsigned x, p, n;
       {
           
           return ((x >> (p+1-n)) & ~(~0 << n));
           
    }

Сказать по правде я совсем не уверен, но может так:

getbits(x,p,n)  /* get n bits from position p */
unsigned x, p, n;
   {
       
       return ((x << (p+1-n)) & ~(~0 >> n));
       
}

Прошу не бить сильно я только учусь, как правильно работать с битами.