Упражнение 2.6.

Напишите функцию setbits(x, p, n, y), возвращающую значение x, в котором n битов, начиная с p-й позиции, заменены на n правых разрядов из y (остальные биты не изменяются).

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

В Си имеются шесть операторов для манипулирования с битами. Их можно применять только к целочисленным операндам, т. е. к операндам типов char, short, int и long, знаковым и беззнаковым.

& — побитовое И.
| — побитовое ИЛИ.
^ — побитовое исключающее ИЛИ.
<< — сдвиг влево.
>> — сдвиг вправо.
~ — побитовое отрицание (унарный).

Оператор & (побитовое И) часто используется для обнуления некоторой группы разрядов.

Например

n = n & 0177;

обнуляет в n все разряды, кроме младших семи.

Число 0177 записано в восьмеричной системе. В двоичной системе это число равно

0000 0000 0000 0000 0000 0000 0111 1111, размер целого на моей машине 4 байта.

Пусть целая переменная n = 65535 

(0000 0000 0000 0000 1111 1111 1111 1111 в двоичном виде)

0000 0000 0000 0000 1111 1111 1111 1111

&

0000 0000 0000 0000 0000 0000 0111 1111

---------------------------------------

0000 0000 0000 0000 0000 0000 0111 1111

#include <stdio.h>
int main(void)
{
    int n = 65535;
    n = n & 0177;
    

    printf("%d\n", n);
}

Восьмеричные числа используются из-за удобства при работе с двоичной системой счисления. Каждая цифра восьмеричного числа может быть заменена тремя цифрами двоичного.

Таблица соответствия цифр восьмеричной системы счисления числам двоичной системы:

0 000

1 001
2 010
3 011
4 100
5 101
6 110
7 111

Оператор | (побитовое ИЛИ) применяют для установки разрядов; так,

х = х | SET_ON;

устанавливает единицы в тех разрядах х, которым соответствуют единицы в SET_ON.

#include <stdio.h>

#define SET_ON 07 /* 0000 0000 0000 0000 0000 0000 0000 0111 */

int main(void)

{

int n = 120; /* 0000 0000 0000 0000 0000 0000 0111 1000 */

n = n | SET_ON;

printf("%d\n", n);

}

0000 0000 0000 0000 0000 0000 0000 0111

|

0000 0000 0000 0000 0000 0000 0111 1000

---------------------------------------

0000 0000 0000 0000 0000 0000 0111 1111

Оператор ^ (побитовое исключающее ИЛИ) в каждом разряде установит 1, если соответствующие разряды операндов имеют различные значения, и 0, когда они совпадают.

#include <stdio.h>

int main(void)

{

int a = 017; /* 0000 0000 0000 0000 0000 0000 0000 1111 */

int b = 036; /* 0000 0000 0000 0000 0000 0000 0001 1110 */

int c = 0;

c = a ^ b;

printf("%o ^ %o = %o\n", a, b, c);

printf("%x ^ %x = %x\n", a, b, c);

}

17 ^ 36 = 21
f ^ 1e = 11

0000 0000 0000 0000 0000 0000 0000 1111

^

0000 0000 0000 0000 0000 0000 0001 1110

---------------------------------------

0000 0000 0000 0000 0000 0000 0001 0001

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

#include <stdio.h>

int main(void)
{
unsigned char a = 11; /* 0000 1011 */
a = a << 2;

printf("The result is %d\n", a);
}

The result is 44

0000 1011    11
<< 2         *4
0010 1100    44

Как видно из примера, освободившиеся биты справа заполнились нулями.

#include <stdio.h>

int main(void)
{
unsigned char a = 11; /* 0000 1011 */
a = a >> 2;

printf("The result is %d\n", a);
}

The result is 2

0000 1011       11
>> 2            /4
0000 0010 11    2

Сдвиг числа на 2 разряда вправо равносилен его делению на 4. Выдвигаемые наружу разряды содержат остаток от деления (11 в двоичной системе = 3 в десятичной; 11 % 4 = 3).

Сдвиг вправо знаковой величины на одних машинах происходит с распространением знака ("арифметический сдвиг"), на других — с заполнением освобождающихся разрядов нулями ("логический сдвиг").

#include <stdio.h>

int main(void)
{
signed char a = -16; /* 1111 0000 */
a = a >> 2;

printf("The result is %d\n", a);
}

The result is -4

1111 0000    -16
>> 2         /4
1111 1100    -4

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

Унарный оператор ~ поразрядно "обращает" целое т. е. превращает каждый единичный бит в нулевой и наоборот. Например

х = х & ~077

обнуляет в х последние 6 разрядов. Заметим, что запись х & ~077 не зависит от длины слова, и, следовательно, она лучше, чем х & 0177700, поскольку последняя подразумевает, что х занимает 16 битов. Не зависимая от машины форма записи ~077 не потребует дополнительных затрат при счете, так как ~077 — константное выражение, которое будет вычислено во время компиляции.

 077 - 0000 0000 0011 1111

~077 - 1111 1111 1100 0000 - 177700 (2 байта)

1111 1111 1111 1111 1111 1111 1100 0000 - 37777777700 (4 байта)

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

#include <stdio.h>

unsigned getbits(unsigned х, int p, int n);

int main(void)

{

printf("%u\n", getbits(126, 4, 3));

return 0;

}

/* getbits: получает n бит, начиная с р-й позиции */

unsigned getbits(unsigned х, int p, int n)

{

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

}

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

Упражнение 2.5.

Напишите функцию any(s1, s2), которая возвращает либо ту позицию в s1, где стоит первый символ, совпавший с любым из символов в s2, либо -1 (если ни один символ из s1 не совпадает с символами из s2).

(Стандартная библиотечная функция strpbrk делает то же самое, но выдает не номер позиции символа, а указатель на символ.)

Упражнение 2.4.

Напишите версию функции squeeze(s1, s2), которая удаляет из s1 все символы, встречающиеся в строке s2.

Операторы инкремента и декремента

В Си есть два оператора, предназначенных для увеличения и уменьшения переменных. Оператор инкремента ++ добавляет 1 к своему операнду, а оператор декремента -- вычитает 1.

Необычность операторов ++ и -- в том, что их можно использовать и как префиксные (помещая перед переменной: ++n), и как постфиксные (помещая после переменной: n++) операторы. В обоих случаях значение n увеличивается на 1, но выражение ++n увеличивает n до того, как его значение будет использовано,
а n++ — после того.

Предположим, что n содержит 5, тогда

x = n++;

установит x в значение 5, а

x = ++n;

установит х в значение 6. И в том и другом случае n станет равным 6.

Операторы инкремента и декремента можно применять только к переменным. Выражения вроде (i+j)++ недопустимы.

Если требуется только увеличить или уменьшить значение переменной (но не получить ее значение), как например

if (c == '\n')
    nl++;

то безразлично, какой оператор выбрать — префиксный или постфиксный.

Но существуют ситуации, когда требуется оператор вполне определенного типа. В качестве примера, авторы книги предлагают рассмотреть функцию
squeeze(s, с), которая удаляет из строки s все символы, совпадающие с c:

#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */

int getstr(char line[], int maxline);
void squeeze(char s[], int с);

int c = 65; /* Символ 'A' */

int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */

while ((len = getstr(line, MAXLINE)) > 0)
{
squeeze(line, c);
printf("%s", line);
}

return 0;
}

/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;

for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
{
s[i] = c;
++i;
}
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}

/* squeeze: удаляет все с из s */
void squeeze(char s[], int с)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != c)
s[j++] = s[i];
s[i] = '\0';
}



#include <stdio.h>
#define MAXLINE 1000 /* максимальный размер вводимой строки */

int getstr(char line[], int maxline);
void squeeze(char line[], int symbol);

int main(void)
{
int len = 0;
char line[MAXLINE]; /* текущая строка */

int c = 65; /* Символ 'A' */

while ((len = getstr(line, MAXLINE)) > 0)
{
squeeze(line, c);
printf("%s", line);
}

return 0;
}

/* getline: читает строку в s, возвращает длину */
int getstr(char s[], int lim)
{
int c, i;

for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n')
{
s[i] = c;
++i;
}
s[i] = '\0'; /* в конец строки дописывам "0" */
return i; /* функция возвращает длину строки */
}

/* squeeze: удаляет все с из s */
void squeeze(char s[], int symb)
{
int i, j;
for (i = j = 0; s[i] != '\0'; i++)
if (s[i] != symb)
s[j++] = s[i];
s[i] = '\0';

}

Каждый раз, когда встречается символ, отличный от с, он копируется в текущую j-ю позицию, и только после этого переменная j увеличивается на 1, подготавливаясь таким образом к приему следующего символа. Это в точности совпадает со следующими действиями:

if (s[i] != с) {
    s[j] = s[i];
    j++;
}

Другой пример — функция getline. Приведенную там запись

if (с == '\n' ) {
    s[i] = с;
    ++i;
}

можно переписать более компактно:

if (с == '\n' )
    s[i++] = с;

В качестве третьего примера рассматривается функция strcut(s, t), которая строку t помещает в конец строки s. Предполагается, что в s достаточно места, чтобы разместить там суммарную строку. strcut написана так, что она не возвращает никакого результата. На самом деле библиотечная strcat возвращает указатель на результирующую строку.

#include <stdio.h>

#define MAXLINE 1000 /* максимальный размер вводимой строки */

int getstr(char line[], int maxline);

void strcut(char line[], char new_line[]);

int main(void)

{

int len = 0;

char line[MAXLINE]; /* текущая строка */

char new_line[] = "This is the end!";

while ((len = getstr(line, MAXLINE)) > 0)

{

strcut(line, new_line);

printf("%s", line);

}

return 0;

}

/* getline: читает строку в s, возвращает длину */

int getstr(char s[], int lim)

{

int c, i;

for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)

s[i] = c;

if (c == '\n')

s[i++] = c;

s[i] = '\0'; /* в конец строки дописывам "0" */

return i; /* функция возвращает длину строки */

}

/* strcut: помещает t в конец s; s достаточно велика */

void strcut(char s[], char t[])

{

int i, j;

i = j = 0;

while (s[i] != '\0') /* находим конец s */

i++;

while ((s[i++] = t[j++]) != '\0') /* копируем t */

;

}

При копировании очередного символа из t в s постфиксный оператор ++ применяется и к i, и к j, чтобы на каждом шаге цикла переменные i и j правильно отслеживали позиции перемещаемого символа.

Упражнение 2.З.

Напишите функцию htoi(s), которая преобразует последовательность шестнадцатеричных цифр, начинающуюся с 0х или 0Х, в соответствующее целое. Шестнадцатеричными цифрами являются символы 0…9, а…f, А…F.

Преобразования типов

Если операнды оператора принадлежат к разным типам, то они приводятся к некоторому общему типу. Приведение выполняется в соответствии с небольшим числом правил. Обычно автоматически производятся лишь те преобразования, которые без какой-либо потери информации превращают операнды с меньшим диапазоном значений в операнды с большим диапазоном, как, например, преобразование целого в число с плавающей точкой в выражении вроде f + i. Выражения, не имеющие смысла, например число с плавающей точкой в роли индекса, не допускаются. Выражения, в которых могла бы теряться информация (скажем, при присваивании длинных целых переменным более коротких типов или при присваивании значений с плавающей точкой целым переменным), могут повлечь за собой предупреждение, но они допустимы.