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

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

дерзайте! победителя угощу мороженным! :)

(билет в Хайфу за свой счёт)

Цитата(cosmic @ 28.9.2002, 04:02)

не используя циклов и рекурсий.

       

Очень просто - целых 3 варианта
1) сравниваем все 8 бит по отдельности, в 8 строк кода
2) Сравниваем все восемь бит по одному в одной строке
3) Как я понимаю переходы по метке к циклам не относятся?

не циклов не рекурсии - задача решена, условия соблюдены!

Vit, бегу за мороженным а что значит 2) и 3)? распиши, пожалуйста, на Си или на чём хочешь, потому как не въехал я.

э... приглядевшись: первое гениально, конечно, но... не то чтобы было жалко мороженного ... разве в байте всегда 8 бит? а? а? э! никуда не бегу, чешу репу, пересчитываю мелочь в кармане

жду идей!

Конечно же в байте 8 бит (не будем учитывать маразм про дополнительный девятый бит - контроль четности).
Как проверить биты думаю объяснять в деталях не надо? (AND с маской и SHR на нужное кол-во бит)
Про метки весьма интересный вопрос.
Будет ли это считаться циклом? (поидее будет)
a:
jmp a
Чтобы получить кол-во ноликов можно все биты сложить 0 ноликов - это будет 8 и соотв. все нолики - это будет 0

Цитата(cosmic @ 28.9.2002, )

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

"Подсчитать" - определить только их количество, или номера тоже?

Цитата(cosmic @ 28.9.2002, 13:25)

Vit, бегу за мороженным а что значит 2) и 3)? распиши, пожалуйста, на Си или на чём хочешь, потому как не въехал я.

Писать буду на Паскале...

1) сравниваем все 8 бит по отдельности, в 8 строк кода

Код

Function GetZeroBitCount(b:byte):byte; begin result:=0; if (b and 1) = 0 then inc(result); if (b and 2) = 0 then inc(result); if (b and 4) = 0 then inc(result); if (b and 8) = 0 then inc(result); if (b and 16) = 0 then inc(result); if (b and 32) = 0 then inc(result); if (b and 64) = 0 then inc(result); if (b and 128) = 0 then inc(result); end;

2) Сравниваем все восемь бит по одному в одной строке

Код

Function GetZeroBitCount(b:byte):byte;  Function Sigh(b:byte):byte;  begin    if b=0 then result:=1 else result:=0;  end; begin result:=Sigh(b and 1)+Sigh(b and 2)+Sigh(b and 4)+Sigh(b and 8)+Sigh(b and 16)+Sigh(b and 32)+Sigh(b and 64)+Sigh(b and 128); end;

или другой вариант, действительно в одну строку:

Код

Function GetZeroBitCount(b:byte):byte; begin result:=8-((b mod 2)+((b div 2) mod 2)+((b div 4) mod 2)+((b div 8) mod 2)+((b div 16) mod 2)+((b div 32) mod 2)+((b div 64) mod 2)); end;

3) Как я понимаю переходы по метке к циклам не относятся?

Код

Function GetZeroBitCount(b:byte):byte;  Label 1;  Var i:byte; begin i:=1; result:=0; 1: if (b and i) = 0 then inc(result); if i<128 then   begin     i:=i*2;     goto 1;   end; end;

Цитата(cosmic @ 28.9.2002, 13:25)

разве в байте всегда 8 бит?

Знаешь, это не теорема, и даже не аксиома, просто принято что 1 байт это 8 бит, примерно так же как 1 метр это 100 сантиметров, а 1 килограм это 1000 грамм. По определению 8 и только 8, и даже девятый бит чётности - это дополнительный флаг, а вовсе не составная часть байта... В общем вся информатика стоит на том что:

1 байт = 8 бит
1 килобайт = 1024 байт
1 мегабайт = 1024 килобайт
1 гигабайт = 1024 мегабайт
1 терабайт = 1024 гигабайт

1 Слово = 2 байта
1 Длинное слово = 4 байта = 2 слова

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

Вот, не то ли это - посмотри, пожалуйста (вторая ф-ция Get_NBits):
(код на СИ, который мне несколько непривычен - извини, если что):

Код

#include <stdio.h> #include <conio.h> typedef unsigned char BYTE, *PBYTE; typedef unsigned int WORD, *PWORD; BYTE Get_Bits(BYTE b) {  BYTE res;  BYTE wb;  int i;  wb=b;  res=0;  for (i=0;i<8;i++)  { res+=wb&1; wb>>=1;  }  return(res); } BYTE Get_NBits(BYTE b) {  BYTE base,base1,base2;  base=(b&0x55)+((b&0xAA)>>1);  base1=(base&0x33)+((base&0xCC)>>2);  base2=(base1&0x0F)+(base1>>4);  return(base2); } void main(void) {  int i;  for (i=0;i<256;i++)  { printf("%u %u %u\n",i,Get_Bits(i),Get_NBits(i)); if (Get_Bits(i)!=Get_NBits(i)) { printf("Error !"); getch(); }  } }

всем привет!

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

идея с восьмикратным повторением кода, [Vit 1], и то же самое "в одну строку" [Vit 2, Baa, Chingachguk], в общем, ясна. этим, как я понимаю, можно воспользоваться и при нахождении первого нулевого бита, так что код приводить не надо. Chingachguk - красиво получилось можно поинтересоваться, а какой язык "родной"?

по поводу [Vit 3]: "мы тут посоветовались с народом и у народа есть мнение..." считать переход по меткам назад (!) циклом. ничего против переходов по меткам вперёд (если будут варианты) не предвижу.

да, для нахождения нулевого бита (в данном случае старшего) я сначала хотел воспользоваться логарифмом по основанию 2, то есть как-то вот так:

short f (BYTE byte)
{
return  log (~ byte) / log (2);
}

а в случае равенства (~ byte) нулю каким-то образом отлавливать ошибку и делать вывод, что все биты = 1. (я прошу прощения, говорю только на Си, ~ - это как бы двоичное дополнение, или как оно там называется). меня только мучает вопрос, как функция логарифма реализована в математической библиотеке. если кто-то в курсе - расскажите.

по-прежнему жду идей. самых бредовых, какие только придут вам в голову... Forth!

э... мда... про наболевшее. про 8 бит.

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

поэтому в принципе, признаю всю критику в мой адрес, но... если кто-нибудь выдаст решение без привязки к цифре "8" или (хотябы) с использованием вместо неё макроопределения CHAR_BIT из файла limits.h в языке Си (аналогов в других языках я не знаю), то я предпочту это решение...

и ещё...
тема Dexter'а "байты и биты"
   Vit: ...я работал на системах с основаниями 5, 6, 7 - увеличение основания происходило с увеличением вычислительной мощности

? хочу комментариев!

а пока можете рассказать, какое мороженное вам больше нравится

Ну таймер используй...

Мля! Хорошая задачка! Попробуем подойти с другой стороны. Как мы вообще можем это сделать?

1) Работать напрямую с битами. Тут нужен доступ к этим битам. Пути решения:
   а) В цикле, рекурсией - не подходит по условию задачи
   б) Простым перечислением - что я и продемонстрировал
   в) Использовать циклы и рекурсию операционной системы, компьютера, среды разработки. Т.е. код циклов не будет содержать, хотя они будут использоваться - например - вызовы таймера, использовать для выполнения повторяющихся действий каких-нибудь событий - например перерисовку формы, вместо рекурсии - создание классов в конструкторе другого класса и т.п. Но фактически приходим к пункту "1.а" - циклы в неявной форме

2) Работать со всем числом целиком
  а) Сравнить с уже известными значениями - ну в общем не сложно - определили массивы с числами... Думаю этот метод не понравится, так же как и 1.б (мне он тоже не нравится)
  б) Специальная математическая формула, позволяющая вычислить количество нулей. Я такой формулы не знаю - все действия с битами проводятся именно над битами и требуют бит за битом проверять - а это либо цикл либо рекурсия... Может кто знает, но я поспрашивал коллег, никто не смог вспомнить такой формулы.

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

Попробуй посмотреть такой вариант - он без привязки к числу бит в байте:

Цитата

#include <stdio.h> #include <conio.h> #define BitsSize 12 /* Размерность переменной в битах */ typedef unsigned int MyBYTE; /* Максимально достаточный тип данных в */ MyBYTE Get_Bits(MyBYTE b) {  MyBYTE res,wb,i;  wb=b;  wb&=(1<<BitsSize)-1;  res=0;  for (i=0;i<BitsSize;i++)  { res+=wb&1; wb>>=1;  }  return(res); } MyBYTE Get_NBits(MyBYTE b) {  MyBYTE wb;  wb=b;  wb&=(1<<BitsSize)-1;  wb=(wb&0x5555)+((wb&0xAAAA)>>1);  wb=(wb&0x3333)+((wb&0xCCCC)>>2);  wb=(wb&0x0F0F)+((wb&0xF0F0)>>4);  wb=(wb&0xFF)+(wb>>8);  return(wb); } void main(void) {  long i;  MyBYTE Old,New;  for (i=0;i<1024;i++)  { Old=Get_Bits(i); New=Get_NBits(i); /* Глючит у меня printf в BC ;) */ printf("%u",i); printf(" %u",Old); printf(" %u\n",New); if (Old!=New) { printf("Error !"); getch(); }  } }

А родной мне язык - ассемблер ;)

ЗЫ: Есть еще один вариант, но он мне не нравится - нельзя сделать условную компиляцию (если число бит - такое-то, то код - такой-то):

Цитата

... #define BitsSize 8 /* Размерность переменной в битах */ #define SizeGreatThan1 #define SizeGreatThan3 #define SizeGreatThan5 typedef unsigned char BYTE; ... BYTE Get_NBits(BYTE b) {  BYTE res;  res=b; #ifdef SizeGreatThan1  res=(res&0x55)+((res&0xAA)>>1); #endif #ifdef SizeGreatThan3  res=(res&0x33)+((res&0xCC)>>2); #endif #ifdef SizeGreatThan5  res=(res&0x0F)+((res&0xF0)>>4); #endif  return(res); } ...

(Тут также минус - константы заданы максимально возможные, что, в принципе, верно - но некрасиво...)

Цитата(Chingachguk @ 01.10.2002, 02:33)

void main(void) {  long i;  MyBYTE Old,New;  for (i=0;i<1024;i++)  { Old=Get_Bits(i); New=Get_NBits(i); /* Глючит у меня printf в BC ;) */ printf("%u",i); printf(" %u",Old); printf(" %u\n",New); if (Old!=New) { printf("Error !"); getch(); }  } }

Вроде бы речь шла о том что надо без циклов, или "for (i=0;i<1024;i++)" в C++ за цикл не считается?

Это проверка ;) Код без циклов в проверяемой процедуре(Get_NBits) ;)

А C++ я еще не пробовал - это си вроде ...