LinuxForum.Fans
Тема

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

Автор: hardorsoft 73 сообщений 11053 просмотров
30.03.2011 16:43 #146152

hardosoft,
нет,

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

не является решением модифицированной задачи. Обратите внимание на сообщение №27 и попытайтесь составить решение.

30.03.2011 16:49 #146154
bormant написал:
не является решением модифицированной задачи. Обратите внимание на Вопрос о побитовых логических операциях. Теория. #162647 и попытайтесь составить решение.

я видимо что-то пропустил в обсуждении, но где условие "модифицированной задачи"?

30.03.2011 17:20 #146167
bormant написал:
http://linuxforum.ru/viewtopic.php?pid=162610#p162610
Модифицированная задача: Переделайте getbits таким образом, чтобы биты отсчитывались слева направо.

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

ЗЫ: маленькая подсказка: sizeof(), без этого маломальски универсальной функции не получится.

30.03.2011 17:35 · отредактировано #146175

hardorsoft,
вот вам в помощь для наглядности вывода значений:

text

void show_value(unsigned x) {
    char buf[36] = { 0 };
    char *c = &buf[34];
    unsigned msk;
    for (msk=1; msk>0; msk<<=1,c--) {
        *c = x & msk ? '1' : '0';
        if (msk&0x808080) *--c=' ';
    }
    printf("%10u(dec), %08x(hex), %s(bin)\n", x, x, buf);
}

пример использования:

text

    show_value(0x7fffffff);
    show_value(x);

пример вывода:

text

2147483647(dec), 7fffffff(hex), 01111111 11111111 11111111 11111111(bin)
30.03.2011 17:41 · отредактировано #146179

Fat-Zer,
задачи базовые, направлены на понимание битовой арифметики, не нужно пока сюда sizeof тащить.
Тем не менее, и исходная, и модифицированная задача имеют не зависящие от sizeof и размерности решения, разве это не очевидно из использованного способа формирования маски ( ~(~0 >> n) ) ?

Кроме того, модифицированная задача интересна как задача на знание C/C++ тем, что имеет один маленький подвох.

30.03.2011 17:45 #146182
bormant написал:
не нужно пока сюда sizeof тащить.

угу. sizeof тут не причём. такое у Кнута на шестибитовых байтах работало :D

bormant написал:
Кроме того, модифицированная задача интересна как задача на знание C/C++ тем, что имеет один маленький подвох.

угу...

30.03.2011 18:22 #146202

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

drBatty написал:
такое у Кнута на шестибитовых байтах работало

если подзакладываться на то, что в байте не 8 бит, то... на этом мысль обрывается... кста, а стандарт определяет константу типа битс-пер-байт?

30.03.2011 18:41 #146212

bormant, я про модифицированную задачу...

30.03.2011 18:48 #146217
Fat-Zer написал:
конечно есть неэффективные способ, но это не считается.

почему способ ~0 "не эффективный"? oO
~0 == системо-независимая константа. И означает "число в котором все биты равны 1". Время вычисления равно нулю. Как и для всех констант. В том числе и ~666*5^-17/cos(PI/3).

Fat-Zer написал:
если подзакладываться на то, что в байте не 8 бит, то... на этом мысль обрывается... кста, а стандарт определяет константу типа битс-пер-байт?

какая разница? Кнут писал программы, которые без всякого изменения работали и на 6и битах и на 8и, и на 777и.
да, а sizeof(char) == 1 по определению. Сколько бит в байте, ЕМНИП, в стандарте не определено.

30.03.2011 18:53 · отредактировано #146221
Fat-Zer написал:
bormant, я про модифицированную задачу...

Там всё точно также. Разбор "на карандаше" я уже приводил: http://linuxforum.ru/viewtopic.php?pid=162647#p162647
Программная реализация на C/C++ требует знания C/C++ (капитан очевидность отдыхает wink ), а у недостаточно его знающих вызовет небольшое затруднение, которое легко может быть устранено путём логических рассуждений и начальных страниц описания C/C++.

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

30.03.2011 19:06 #146226
bormant написал:
Какого рода это затруднение -- пока оглашать не не буду

ЕМНИП, когда я лет 15 назад решал эту задачу, у меня было 2 затруднения:
1) как-то не слишком интуитивно понятно, что сначала выполняется, что потом. Надо либо кучу скобок, либо кучу временных переменных. Сейчас это не играет роли - компилятор всё лишнее выкинет.
2) не сразу сообразил, как маску сделать, что-бы при любом числе бит взлетело.

30.03.2011 19:28 #146236
bormant написал:
Там всё точно также. Разбор "на карандаше" я уже приводил: Вопрос о побитовых логических операциях. Теория. #162647
Программная реализация на C/C++ требует знания C/C++ (капитан очевидность отдыхает ), а у недостаточно его знающих вызовет небольшое затруднение, которое легко может быть устранено путём логических рассуждений и начальных страниц описания C/C++.

здесь биты сдвигаются в конец и это очевидное решение... а если сдвигать биты в начало, то без sizeof'а не получится...

drBatty написал:
какая разница? Кнут писал программы, которые без всякого изменения работали и на 6и битах и на 8и, и на 777и.
да, а sizeof(char) == 1 по определению. Сколько бит в байте, ЕМНИП, в стандарте не определено.

по поводу кнута: у любого алгоритма есть придел на котором он перестаёт работать и нужны изменения... особенно алгоритмы манипуляции с битами.
по поводу константы: не про то спрашивал... зовётся она CHAR_BIT.

drBatty написал:
почему способ ~0 "не эффективный"?
~0 == системо-независимая константа. И означает "число в котором все биты равны 1". Время вычисления равно нулю. Как и для всех констант. В том числе и ~666*5^-17/cos(PI/3).

я не писал, что ~0 - неэффективно.

30.03.2011 19:45 #146242
Fat-Zer написал:
по поводу кнута: у любого алгоритма есть придел на котором он перестаёт работать и нужны изменения...

всё с точностью наоборот: нету никаких пределов у практически всех алгоритмов. Предел есть в реализации этого алгоритма. Или - нету.

Fat-Zer написал:
я не писал, что ~0 - неэффективно.

а какую вам надо константу? отловить, когда биты в начало нельзя будет пихать? т.е. x & 1 у вас работает, и истинно тогда и только тогда, когда младший бит == 1? Вам надо старший? 0x80000000 Это? (для 32х)
А чуть подумать?
1) имеем 00000000
2) ~0 = FFFFFFFF
3) ~0 >> 1 = 7FFFFFFF
4) ~(0 >> 1) = 80000000
5) PROFIT

30.03.2011 19:50 · отредактировано #146247

Fat-Zer,
у меня закрадывается подозрение, что вы говорите о немодифицированной задаче, поэтому уточню ссылки разбора "на карандаше":
немодифицированная задача: http://linuxforum.ru/viewtopic.php?pid=162556#p162556
модифицированная задача: http://linuxforum.ru/viewtopic.php?pid=162647#p162647

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

Вот если задачу ещё модифицировать таким образом, что
1) биты считать справа налево, а результат выводить в старших битах (которые левее),

text

            3          2          1
Биты:      10987654 32109876 54321098 76543210
знач.:     01010101 01010101 01010101 01010101
выбор:                                ^^^^
вывод:     01010000 00000000 00000000 00000000
           ^^^^

2) биты считать слева направо, а результат выводить в старших битах (которые теперь правее)

text

                      1          2          3
поз:       01234567 89012345 67890123 45678901
знач.:     01010101 01010101 01010101 01010101
выбор:                                ^^^^
вывод:     00000000 00000000 00000000 00000101
                                          ^^^^

тогда размер значения в битах был бы нужен. Но такой задачи никто не ставил wink

ps. ... был бы нужен для решения "в лоб". Но, опять таки, можно решить и без sizeof. Попробуйте, это не сложно.

30.03.2011 19:59 #146255
bormant написал:
тогда размер значения в битах был бы нужен.

Вот сложно его один раз вычислить, и присвоить его глобальной константе.

text

int clk_bits_in_int()
{
  int b = 1;
  int x = 1;
  while(x <<= 1)
    b++;
  return b;
}

static const int BITS_IN_INT = clk_bits_in_int();

ну как-то так..

в вашем случае иначе-то никак, ибо компилятор, ЕМНИП, и не знает, сколько у нас будет интов...

30.03.2011 20:24 #146267
drBatty написал:
всё с точностью наоборот: нету никаких пределов у практически всех алгоритмов. Предел есть в реализации этого алгоритма. Или - нету.

я и говорю о реализации на конкретном ЯП на конкретной железке.

drBatty написал:
а какую вам надо константу? отловить, когда биты в начало нельзя будет пихать? т.е. x & 1 у вас работает, и истинно тогда и только тогда, когда младший бит == 1? Вам надо старший? 0x80000000 Это?

я писал про то что найти p n-x бит слева, а потом сдвинуть их в начало (вправо) без sizeof не получится.

bormant написал:
у меня закрадывается подозрение, что вы говорите о немодифицированной задаче, поэтому уточню ссылки разбора "на карандаше":

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

drBatty написал:
Вот сложно его один раз вычислить, и присвоить его глобальной константе.

можно, но не нужно. оно есть в стандарте (в limits.h): CHAR_BIT*sizeof(int)

30.03.2011 20:46 #146281
Fat-Zer написал:
я писал про то что найти p n-x бит слева, а потом сдвинуть их в начало (вправо) без sizeof не получится.

почему? ещё раз поточнее: найти n бит слева, и сдвинуть их все вправо не получится? Почему?
по одному биту - легко.

30.03.2011 20:51 · отредактировано #146288
drBatty написал:
почему? ещё раз поточнее: найти n бит слева, и сдвинуть их все вправо не получится? Почему?
по одному биту - легко.

а на это как раз есть оговорка про неэффективный способ, которую вы цитировали. фраза целиком:

Fat-Zer написал:
не вижу решение без sizeof() или каких-то магических чисел. Нам нужно не только выделить биты, но и сдвинуть их в начало... конечно есть неэффективные способ, но это не считается.
Войдите или зарегистрируйтесь, чтобы ответить.