Ошибки при сборке тренировочного задания по C

вроде, тоже к слову «точность» подходит

Нет.
Степень малости (отрицательный порядок) на степень точности (количество значащих цифр) не влияет.

Продолжаем постигать Си: «константы перечислимого типа» и enum. В параграфе, посвящённом этому, есть такие слова:

«Хотя можно объявлять переменные типов enum, компиляторы не обязаны проверять, допустимые ли значения хранятся в таких переменных. Тем не менее, переменные перечислимых типов предоставляют возможность такой проверки и потому часто бывают удобнее директив #define»

В учебнике приведён пример:

enum months { JAN = 1, FEB, MAR };

Тем не менее, переменные перечислимых типов предоставляют возможность такой проверки

Вот это не понял целиком. Что значит, что переменная предоставляет возможность проверки, в контексте того, что компилятор эту проверку не выполняет? Переменная перечислимого типа - это и есть переменная типа enum? А что тогда есть «константа перечислимого типа»? Набор пар «символическое имя — значение»? Пожалуйста, если тебе не трудно, помоги разобраться в этой теме.

enum months это перечислимый тип. JAN, FEB, MAR это константы этого типа. var это переменная этого типа:

enum months var;

По идее, переменные этого типа не должны принимать значения, отличающиеся от этих констант и компилятор может эти ситуации отловить, если присваиваемое выражение имеет другой тип (также в switch по перечислению, в котором нету каких-то значений, компилятор может сообщить об этом). Но реальных ограничений тут нет и такие переменные могут содержать что-то вне области констант, GCC предполагает такой расклад:

int
func(enum months var)
{
    switch (var) {
        case JAN:
        case FEB:
        case MAR:
            return 0;
    };
    // GCC с соответствующими флагами требует return здесь и мы сюда попадём, если var не был инициализирован, например.
    return 1;
}

Так. Правильно ли я понимаю, что если я сделаю

enum name {value1, value2, value3};

то я так создам новый тип enum name, и переменные этого типа, которые я буду позже объявлять с помощью

enum name variable1, variable2, variable3, variable4

могут (в идеале, но реальных ограничений нет) принимать только значения, определённые в фигурных скобках

value1, value2, value3

в виде символической константы (с автоматически выбранным значением) или в виде пары константа-значение?

Если да, то тогда мне не совсем ясно, какому «привычному» типу (char, int, float...) соответствует свежеобъявленный тип. В примере из учебника константы в фигурных скобках соответствовали целым числам. Там принципиально могут быть только они, т.е. типы int, short, long, char (кстати, кто именно из них?), или что угодно?

google: n1256.pdf (ISO/IEC 9899:TC3)

Если да, то тогда мне не совсем ясно, какому «привычному» типу (char, int, float...) соответствует свежеобъявленный тип. В примере из учебника константы в фигурных скобках соответствовали целым числам. Там принципиально могут быть только они, т.е. типы int, short, long, char (кстати, кто именно из них?), или что угодно?

Всё тут абсолютно ясно:

6.7.2.2 Enumeration specifiers абзац 2
The expression that defines the value of an enumeration constant shall be an integer constant expression that has a value representable as an int.

не благодари

Не надо это путать с макросами препроцессора. enum это их аналог только для целочисленных значений. Реальный тип будет целочисленным, но его размерность определяется компилятором исходя из диапазона значений (т.е. может быть любой из char, short, int, long, long long).

Кажется, принцип до меня дошёл. А в чём принципиальное преимущество перед #define, кроме автоматического заполнения и проверки, которой почти нет? Или я всё-таки неверно понимаю назначение сабжа?

Хоть какая-то типизация (не целое значение не пройдёт). С ней компилятор может сделать что-то полезное, а без неё ничего не сможет в принципе.

Плюс ошибки компиляции будут адекватнее, да и препроцессор пролезет всюда, а перечисление просто будет во внешнем scope и не сломает компиляцию. Т.е. оно немного безопаснее (в том же инициализаторе можно не ставить скобки для сложных выражений, где макросы при подстановке поменяют семантику без этих же скобок).

Понял, спасибо

Снова я. Из учебника: https://i.imgur.com/sYlQdVC.png

Суть операции мне ясна. x = x & ~077 делает следующее:

• 077 - это восьмеричное число 77, равное 111111 с незначащими нулями слева в двоичном виде.
• ~077 заменяет в 111111 все нули на единицы и наоборот, т.е. получаются единицы и 6 нулей в конце.
• Операция & зануляет 6 последних бит числа x (остальное остаётся неизменным, т.к. в ~077 там единицы).

Про независимость от длины слова тоже вроде понял: фишка как раз в тех незначащих нулях, которые превращаются в единицы. С таким подходом x может быть числом, состоящим из любого кол-ва разрядов. Но вот почему x & 0177700 опирается на то, что x - 16-разрядная величина? Я предполагаю, что незначащие нули тут тоже есть, и & на такое число занулит 6 последних бит и все разряды, старше 16-го. Или я что-то не так понимаю?

Но вот почему x & 0177700 опирается на то, что x - 16-разрядная величина?

10 единичных + 6 нулевых бит в константе. Имеется в виду это. А если x не 16-бит, то всё поломается, поэтому и опирается.

10 единичных и 6 нулевых - это в 0177700, и x должен тоже иметь 16 разрядов, чтобы всё было хорошо?

А как тогда обстоят дела с ~077? 077 имеет 6 единичных и 0 нулевых, а ~077..?

Что такое «~»?

10 единичных и 6 нулевых - это в 0177700, и x должен тоже иметь 16 разрядов, чтобы всё было хорошо?

Ну да, все биты должны быть учтены.

А как тогда обстоят дела с ~077? 077 имеет 6 единичных и 0 нулевых, а ~077..?

077 имеет 6 единичных и (N - 6) нулевых, где N - размер int в битах. При этом единица в знаковом разряде будет размножаться при расширении типа, так что реальный размер особо не важен.

С таким подходом x может быть числом, состоящим из любого кол-ва разрядов.

Вот это в предыдущем комментарии правильно.

А почему не может 0177700 выглядеть, как 10 единичных, 6 нулевых в конце и N-16 нулевых в начале и работать нормально с X длиной больше 16 разрядов, зануляя все позиции, кроме тех, где у 0177700 стоят единицы?

Если я правильно это такая операция, которая, будучи применённой к X, даёт такое число, что X + это_число даёт число с тем же кол-вом разрядов, что и X, с единицей в каждом разряде. Т.е. в том месте, где у X нули, у нового числа - единицы и наоборот, длина совпадает.

Верно, хоть и переусложнено слегка. Это инверсия всех битов. Этого знания уже хватает, чтобы понять, чему будет равно ~077 на машинах с разной длиной слова.

Если в уме пока плохо получается, попробуй на бумаге расписать. Это помогает.

зануляя все позиции, кроме тех, где у 0177700 стоят единицы?

Так оно и будет работать. Но цель-то была занулить последние 6 бит.

А, т.е. оно по-прежнему работает для X длиной больше 16 бит, но не так, как хотелось? Тогда ясно.

А ~077, оно же ~111111, будет равно 111...111000000, так, что заполнено все место, отведённое под тип. Именно поэтому сработает нормально для иксов любой длины, ведь изменятся только последние 6 разрядов, умножение на единицу ничего не меняет. Догнал, кажется) Спасибо!

Оно то работать будет, но это какая-то странная маска получается и скорее является ошибкой в коде чем чем-то полезным (может работать до тех пор пока биты в старших разрядах не используются, а потом проявится в виде бага).

Ага, теперь понял. Я почему-то успел забыть о начальной цели (занулить последние 6) и рассматривал ~077 и 0177700 по отдельности xD

А вот и снова я. На этот раз у меня вопросов нет, но я наткнулся на задание, которое показалось мне сложнее, чем предыдущие. Суть: написать функцию setbits(x, p, n, y) так, чтобы она возвращала свой аргумент x, в котором n битов, начиная с позиции p, равны n крайним правым битам аргумента y, а остальные биты не тронуты. В процессе написания функции мне пришлось не только освоить gdb, но и использовать параллельно gdb и карандаш с блокнотом, сверяя значения переменных с ожидаемым мною от алгоритма результатом. В итоге получился вот такой код (проверил для нескольких наборов разных данных, они фиксируются в вызове setbits в printf): https://gist.github.com/anonymous/ea8d8d97da880f668c38d569a1591a62

Всё, в принципе, работает, но, если тебе не трудно, не мог бы ты глянуть, и, может быть, высказать какую-нибудь критику? Заранее спасибо.

power(2, n) эквивалентно 1 << n.

Здесь:

tailX = x & (power(2, p - n + 1) - 1);

tailX = x & (power(2, p) - 1);

И кажется проще не сдвигать x, а сдвигать маску и биты из y, тогда не нужно восстанавливать потерянные биты.

power(2, n) эквивалентно 1 << n.

Ага, то есть, можно использовать << вместо возведения двойки в степень, и таким образом убрать функцию power целиком.

tailX = x & (power(2, p - n + 1) - 1);

У меня тут хвост - то, что надо запомнить и воспроизвести потом обратно. p - n + 1 — это всё до того фрагмента, который я буду заменять, не включая этот фрагмент, ибо сам он мне уже не понадобится.

И кажется проще не сдвигать x, а сдвигать маску и биты из y, тогда не нужно восстанавливать потерянные биты.

Ага, что-то мне такая мысль в голову не пришла. Попозже попробую переделать в таком ключе. Спасибо большое!

У меня тут хвост - то, что надо запомнить и воспроизвести потом обратно. p - n + 1 — это всё до того фрагмента, который я буду заменять, не включая этот фрагмент, ибо сам он мне уже не понадобится.

Мы, видимо, с разных сторон биты считаем. Обычно нулевой это самый правый/младший, тогда позиция равна длине хвоста.

А, понял. Я знаю, что нулевой - это самый правый, но от позиции я почему-то отмерял вправо. Видимо, стоило отмерять влево, по возрастанию номера разряда. :-)

Переделал, как мне кажется, правильно: https://gist.github.com/anonymous/1081e9b0dfa92855eb09343244547eda

Ага. zeroingMask можно было иначе посчитать, если сделать маску средних бит и инвертировать её. Тогда оно было бы более единообразно с вычислением replacingBits и операций, вроде, меньше бы было. Но так тоже правильно.

zeroingMask = ~(((1 << n) - 1) << p);

Ага?

Да, я так имел в виду.

Снова я. У меня тут возникли затруднения с заданием: первые n битов числа x переставить в конец числа. Т.е, например, чтобы для x = 101110101 и n = 5 ответ был 101011011. Первые n битов легко берутся через x & (2^n - 1). Сдвинуть оставшиеся биты в начало легко можно с помощью x >> n, но потом, вроде, надо те самые первые n битов сдвинуть влево так, чтобы пристроить их после сдвинутых оставшихся битов, а мне неизвестно, на сколько надо сдвигать. Я могу, конечно, взять логарифм по основанию 2 от того, что сдвинул в начало, округлить его вверх и получить нужное число, но параграф не о математических функциях, и введения в них ещё не было, поэтому этот вариант мне не кажется подходящим. В качестве костыля можно свою приблизительную реализацию логарифма сделать (делить на 2, пока результат > 1, с увеличением счётчика на 1 после каждого деления), но всё равно мне кажется, что тут надо без алгебры обходиться, использовать только битовые операции. Не мог бы ты подсказать мне, в каком направлении думать? Заранее большое спасибо.

Размер типа известен на этапе компиляции, это зависимость от конкретного типа данных, но иначе никак. Нужно использовать sizeof.

Размер типа - это кол-во бит под переменные этого типа? Тут же вроде не он нужен, а размер в смысле кол-ва значащих бит конкретной переменной.

Размер типа - это кол-во бит под переменные этого типа?

Да.

Тут же вроде не он нужен, а размер в смысле кол-ва значащих бит конкретной переменной.

Я понял как просто старшие биты, даже если они и не используются. Иначе можно битхаками вроде описанных в Hackers Delight определить количество активных бит, но не думаю, что это подразумевалось.

Тогда я, наверное, просто свою примитивную реализацию логарифма сделаю, для решения задачи хватит.

Размер типа - это кол-во бит под переменные этого типа?

Нет, количество байт. А размер байта почти всегда и везде 8 бит https://stackoverflow.com/questions/9727465/will-a-char-always-always-always-.... В <limits.h> определен макрос CHAR_BIT который отвечает на вопрос «сколько бит в байте?»

у kr та глава из которой задание с вращением битов в качестве элементарных операций данны сдвиги левый и правый - и указано что правый сдвиг может поразному(оставленно на долю реализации) заполнять ведущий бит.

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

так что троллинг направлен на лиц не видящих данную главу из k&r и/или не знающих содержания k&r

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

можно через свой rotation которой через младший бит и сдвиг вправо и помещение ранее сохранённого младшего бита в старший бит сдвинутого безобразия. и так N раз

Ну, я сделал так. Работает, вроде: https://gist.github.com/anonymous/62cc9dbf4ba2e38d3b783e862e298f35

если развлекаться и есть только сдвиг то

если битности хватает можно не А двигать а ААА на нужное число бит

тогда средний элемент будет циклическим на нужное число бит

В учебнике есть пример функции поиска нужного значения в упорядоченном массиве с помощью дихотомии, и есть задание, которое гласит: «В нашем двоичном поиске каждый цикл содержит две проверки, тогда как достаточно было бы одной (зато взамен их потребовалось бы больше снаружи цикла). Напишите функцию с одной проверкой внутри цикла и сравните быстродействие (затраты времени).»

Вот функция, как она приведена в учебнике:

/* binsearch(x, v, n): поиск x в v[0] <= v[1] <= ... <= v[n-1] (версия K&R) */
int binsearch(int x, int v[], int n) {
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

Сам я не смог придумать другой реализации (с одной проверкой внутри цикла) и полез искать решения, нашёл вот такой вариант:

/* binsearch2(x, v, n): поиск x в v[0] <= v[1] <= ... <= v[n-1] (версия с одной проверкой внутри цикла) */
int binsearch2(int x, int v[], int n) {
    int low, high, mid;

    low = 0;
    high = n - 1;
    mid = (low + high) / 2;
    while (low <= high && x != v[mid]) {
        if (x < v[mid])
            high = mid - 1;
        else
            low = mid + 1;
        mid = (low + high) / 2;
    }
    if (x == v[mid])
        return mid;
    else
        return -1;
}

Меня сразу смутила мысль о том, что они, с точки зрения кол-ва проверок, одинаковые. Да, во втором варианте проверка x != v[mid] находится не в теле цикла, но является частью условия, которое проверяется перед каждым входом в цикл, так что, количество проверок в первой и во второй функции, вроде, одинаковое, +-1 проверка. Когда же я выполнил по очереди программы, работающие с первой и второй функцией соответственно, и замерил время их работы с помощью time, time везде показал по нулям - программы выполнились мгновенно. В связи со всем этим у меня возникло несколько вопросов:

• Что же имели в виду авторы, когда говорили о варианте с одной проверкой внутри цикла?
• Как следовало написать эту функцию, чтобы она работала максимально эффективно?
• Как можно сравнить скорость работы разных реализаций одного и того же, если время работы в любом случае очень мало?

Не мог бы ты помочь мне разобраться в этой ситуации? Заранее огромное спасибо.

У меня вот так получалось:

int binsearch(int x, int v[], int n)
{
    int high = n - 1;
    int low = 0;
    int mid;

    while (low + 1 < high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else
            low = mid;
    }

    if (x == v[high])
        return high;

    if (x == v[low])
        return low;

    return -1;
}

Что же имели в виду авторы, когда говорили о варианте с одной проверкой внутри цикла?

Аноним написал вариант. Способов записать несколько, ошибиться тоже есть где. Смысл таких вариантов иногда в детерминированной обработке массивов с повторяющимися элементами, когда всегда будет возвращён либо крайний правый либо крайний левый из одинаковых.

Как следовало написать эту функцию, чтобы она работала максимально эффективно?

С одной проверкой внутри должно быть эффекривнее чем с двумя. Ещё используют подобные микрооптимизации условий цикла, но наизусть не помню какие. Дальше оптимизировать мало вариантов, тело цикла уже маленькое.

Как можно сравнить скорость работы разных реализаций одного и того же, если время работы в любом случае очень мало?

Делать не один поиск, а, скажем, 10 млн. поисков. Для точного сравнения много чего выдумывают, есть целые статьи с рекомендациями, но многократного повторения для таких задач на интерес хватит (можно ещё сначала прокрутить пару сотен тысяч для «разогрева», но тогда замерять надо будет уже в коде).

Спасибо! Вник и понял :)

В вариант анонима я вник и суть понял. Что касается проверки скорости - так впредь и буду делать, спасибо. Хочется сразу писать оптимальный код, ведь вдруг когда-нибудь написанное реально будет выполняться много раз и нюансы будут играть большую роль.

У меня возникла пара вопросов насчёт оформления кода. В K&R функцию main определяют просто как

main() { ...

Я знаю, что main возвращает значение типа int, но int перед main опускается, потому что, если тип возвращаемого значения не указан явно, он считается равным int. Я для изящества и единообразия определяю main с помощью

int main() { ...

Правильно ли я понимаю, что такой вариант как минимум ничем не хуже, чем просто main?

И ещё: я прочитал, что для указания на то, что функция не принимает никаких аргументов, можно указывать void в списке аргументов при написании прототипа или при определении функции. В то же время, в K&R используются просто пустые скобки. Какой из этих вариантов является более правильным?

Правильно ли я понимаю, что такой вариант как минимум ничем не хуже, чем просто main?

Вариант без типа возвращаемого значения объявлен deprecated, так что стоит указывать.

Какой из этих вариантов является более правильным?

Писать (void), () означает, что функция принимает любые аргументы (если в C11 ничего не поменялось, но, вроде, не меняли).

Т.е лучший вариант -

int main(void)

, да?

Для main без параметров — да.

А для всего остального без параметров?

Тоже с (void). Просто у main() же как минимум две разные сигнатуры.