Задача на побитовые операции

Доброго времени суток!
Решаю задачи на Си по К&R.
Никак не получается разобраться с побитовыми операциями.


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

Пожалуйста, помогите разобраться.

идея такова: двигаете единицу влево. Когда число обнулится, значит мы вышли за разрядную сетку.

ЗЫ: IRL эта константа равна sizeof(int)*CHAR_BIT. CHAR_BIT - константа определённая в <limits.h>

hardorsoft написал:

Напишите программу для функции wordlength(), вычисляющей длину слова используемой машины

[log2(~0)]+1

drBatty, Вы можете дать ссылку на литературу по побитовым операциям, где все объяснено яснее чем у K&R?

hardorsoft написал:

Вы можете дать ссылку на литературу по побитовым операциям, где все объяснено яснее чем у K&R?

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

/*
  Напишите программу для функции wordlength(), вычисляющей длину слова
  используемой машины, т.е. Число битов в переменной типа int. Функция
  должна быть переносимой, т.е. Одна и таже программа должна правильно 
  работать на любой машине
*/
#include <stdio.h>
wordlength(int x)
{
  int i;
  
  i = ~0;
  printf("www = %i\n", i);
  i = 1;
  while(( x = x >> 1) != 0)
  {
    i++;
    printf("i = %i\n",i);
  }
  printf("%i", i); //*/
}
main()
{
  int x;
  printf("Введите число -> ");
  scanf("%i", &x);
  wordlength(x);
}

Спасибо вы мне очень помогли.... Учиться думать самому. :-)

вообще этот код вычисляет не длину слова, а где в x встречается старшая единица... короче log2(x)

Про Log я еще ничего не читал. По логике не должно быть никакого log.
программу проверял на разных числах все вроде правильно. (?)

hardorsoft написал:

Про Log я еще ничего не читал. По логике не должно быть никакого log.
программу проверял на разных числах все вроде правильно. (?)

эмм... вы понимаете, что значит "длина слова"?

Нет, пока, судя по теме, не понимает. Но знает, ибо в условии об этом написао недвусмысленно. Если бы вместо int был взят char (знаковый и беззнаковый), то начинающему на этих примерах, полагаю, переполнения при переходах через 127, -128, 0, 255 осознать было бы легче, чем многозначные пределы 4-байтного знакового целого.

hardorsoft,
напишите переносимые функции, которые считают количество бит в char и unsigned char, возможно, это окажется проще для понимания идеи и самого процесса.

hardorsoft написал:

Про Log я еще ничего не читал. По логике не должно быть никакого log.

почитайте. на самом деле это просто. Например максимальное число в 32х битах будет 2^32-1. Потому, что-бы узнать длину слова, необходимо и достаточно:

1) создать максимальное число ( в си это ~0)
2) вычислить операцию обратную возведению в степень. А это и есть логарифм.
3) прибавить к нему 1. Ибо [log2(2^n-1)] + 1 == log2(2^n) == n

логарифм переносимо считается например так:
unsigned type x = 1;

int l = 0;
while(x)
{
    x <<= 1;
    l++;
}

(этот код даёт длину типа type. Тип конечно целый.)

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

надо помнить лишь две вещи:
1) в знаковом типе при сдвиге вправо получается из

11111100000000
11111110000000

(знак размножается)
2) в беззнаковом из
11111100000000
01111110000000
(знак в беззнаковом всегда равен 0 (+))

доктор, вам прямо приспичило на все детские задачки ответы написать)))

ЗЫ: первый способ будет работать с любым типом (и со знаковым и с беззнаковым)

Fat-Zer написал:

доктор, вам прямо приспичило на все детские задачки ответы написать)))

ЗЫ: первый способ будет работать с любым типом (и со знаковым и с беззнаковым)

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

drBatty написал:

Если в стандарте написано(?)

сдвиг влево и для знаковых и для без знаковых одинаковый, как ни крути...
а вот по поводу сдвига вправо, если в старшем разряде единица и тип знаковый, то стандарт говорит implementation-defined... gcc на x86 работает как тут http://linuxforum.ru/viewtopic.php?pid=182353#p182353

эхх... я на это напоролся недавно...

Fat-Zer написал:

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

ой ли? на ВСЕХ архитектурах?

Fat-Zer написал:

а вот по поводу сдвига вправо, если в старшем разряде единица и тип знаковый, то стандарт говорит implementation-defined...

разве? честно говоря - не помню.

Fat-Zer написал:

gcc на x86 работает как тут Задача на побитовые операции #182353

да, в x86 есть знаковый и без-знаковый сдвиг. Но есть CPU где только беззнаковый (или только знаковый).

Fat-Zer написал:

эхх... я на это напоролся недавно...

что-бы не влетать так, используйте простое правило:
при всех побитовых операциях (в т.ч. поля и сдвиги) ВСЕГДА используйте тип без знака!
смешно...

быдлокодер написал:

struct MY_BOOL{
int data :1;
};
enum {FALSE,TRUE};

не работает. :(

drBatty написал:

ой ли? на ВСЕХ архитектурах?

1) это говорит стандарт Си
2) а как он может ещё выполнятся? слева биты исчезают, справа появляются нули...

drBatty написал:

при всех побитовых операциях (в т.ч. поля и сдвиги) ВСЕГДА используйте тип без знака!

проскочило в одном месте...

drBatty написал:

не работает.

не понял шутку юмора...

Fat-Zer написал:

1) это говорит стандарт Си

лень проверять. верю wink

Fat-Zer написал:

2) а как он может ещё выполнятся? слева биты исчезают, справа появляются нули...

+11110000000
<<
+11100000000
или
111000000000

проверять лениво...
(IRL я так никогда не напишу)

Fat-Zer написал:

не понял шутку юмора...

целое поле в 1 бит равно нули, или (ВНЕЗАПНО) минус один.
А у нас TRUE получается == 1. Т.о., для нашего типа
MY_BOOL::data x = TRUE
x == -1
x != TRUE
:(

drBatty написал:

лень проверять. верю

зря smile ... ошибся я, для знаковых, если результат выходит за разрядную сетку стандарт говорит UB

drBatty написал:

целое поле в 1 бит равно нули, или (ВНЕЗАПНО) минус один.
А у нас TRUE получается == 1. Т.о., для нашего типа
MY_BOOL::data x = TRUE
x == -1
x != TRUE

мда... до такого я бы не додумался smile

Fat-Zer написал:

мда... до такого я бы не додумался

да я тоже понять не мог - вроде в одном бите 0 или 1, это для меня само собой, а там ВНЕЗАПНО не ноль, и не один :[ часов 5 не понимал, _где_ ошибка :(

ошибся я, для знаковых, если результат выходит за разрядную сетку стандарт говорит UB

даже так... А вообще - << и >> это ИМХО самый главный недостаток Си :(
Совершенно дикое и непредсказуемое поведение. :(