/*
* 12.6.1.c
*
* Created on: 01.05.2009
* Author: egd
*/
#include <stdio.h>
int size_int;
void int_size (void) {
unsigned int a = ~0;
for ( size_int = 0; a != 0; ++size_int)
a >>= 1;
}
int bitpat_search (unsigned int source, unsigned int pattern, unsigned int n) {
int i, j, bit_s = 1, bit_p = 1;
unsigned int s1, p1;
for (i = 0; i != size_int; ++i) {
if ((source & 1) == (pattern & 1)) {
for (j = 1; j != n+1; ++j) { //j = 1 - первый бит мы уже нашли, начинаем со второго
if ((source & bit_s << 1) != (pattern & bit_p << 1))
break;
else if (j == n)
return i;
}
bit_s = 1;
bit_p = 1;
}
source >>= 1;
}
return -1;
}
int main (void) {
void int_size (void);
int bitpat_search (unsigned int source, unsigned int pattern, unsigned int n);
int_size();
printf("%i \n", bitpat_search (0xe1f4, 0x5, 3));
return 0;
}
меняем строку for (j = 1; j != n+1 ; ++j) на for (j = 0; j != n; ++j) - функция возвращает -1
меняем строку for (j = 1; j != n+1 ; ++j) на for (j = 1; j != n; ++j) - функция возвращает -1
меняем строку for (j = 1; j != n+1 ; ++j) на for (j = 0; j != n+1; ++j) - функция возвращает 2
что за магия такая? компилировал в Eclipse
«Когда истинный гений появляется в этом низком мире, его можно узнать по тому знаку, что все глупцы объединяются против него»
ЭЖД вы хотите сказать, что при компиляции одного .cpp файла получается одна программа, а при компиляции другого, бит-в-бит совпадающего с ним .cpp файла получается другая программа?!
ЭЖД вы хотите сказать, что при компиляции одного .cpp файла получается одна программа, а при компиляции другого, бит-в-бит совпадающего с ним .cpp файла получается другая программа?!
я хочу сказать, что если в этой строке поменять вместо n+1 на n то будет -1. в любом случае.
изменение инициализирующего значения для j не влияет на возвращаемое значение.
«Когда истинный гений появляется в этом низком мире, его можно узнать по тому знаку, что все глупцы объединяются против него»
for (j = 1; j != n; ++j) { //j = 1 - первый бит мы уже нашли, начинаем со второго
if ((source & bit_s << 1) != (pattern & bit_p << 1))
break;
else if (j == n)
return i;
Если у Вас до !=n цикл идет, то при j==n в цикл захода не будет, а в функции только два ретурна, этот - гарантированно не выполняется, значит отработает return -1. (Теоретически еще зависнуть может, но не в данном случае). Логично?
PS А что за такой страшный поиск? Не проще идти просто масками, а не побитово?
int bitpat_search (unsigned int source, unsigned int pattern, unsigned int n) {
unsigned int mask = ( 1 << n ) - 1;
for( unsigned int k = 0, ss = source; k < size_int; k++, ss >>= 1 ) {
if( ( ss & mask ) == ( pattern & mask ) )
return k;
}
return -1;
}
Где там?
Так вроде это и делается. Возвращает смещение pattern в source. Последний параметр - длина паттерна в битах.
это задачка из книжки Кочан "Програмиирование на языке С". нужно найти номер бита в source с которого начниается последовательность битов pattern, n - кол-во битов в pattern
/me мало опыта
так проще и быстрее в разы
ну и имхо понятнее.
идея в том, что XOR даёт нуль тогда и только тогда, когда аргументы совпадают, причём мы сравниваем всё, но не все биты нам интересны, потому мы сбрасываем (x &= mask) все не интересные биты. Если интересные биты все 0, то x == 0, и мы нашли pattern. Иначе двигаем образец и маску, и ищем снова.
int bitpat_search (unsigned int source, unsigned int pattern, unsigned int n) {
unsigned int mask = ( 1 << n ) - 1, k;
for( k = 0; k < size_int /*здесь кстати открытым остается вопрос с ведущими нулями*/; k++, source >>= 1 ) {
if( ( /*раз ss не надо тогда */ source & mask ) == pattern )
return k;
}
return -1;
}
Насчет ведущих нулей:
если в 11...1 (0xffff) искать 011 (0x3), длина паттерна - 3, то будет найдено вхождение начиная с 30 бита, т.к. теоретически перед 1 идут нули. Если же надо ограничить только 32 битами, тогда цикле:
NickLion ваш - нормальный. плох тот что в книжке - кривой, нелогичный, и не оптимальный. особенно расстроило то, что в книжке по 1 биту сравнивается. ИМХО это намного сложнее, в том числе и для понимания. Работа с битами это вообще ИМХО слабая сторона Си.
ваш - нормальный. плох тот что в книжке - кривой, нелогичный, и не оптимальный. особенно расстроило то, что в книжке по 1 биту сравнивается. ИМХО это намного сложнее, в том числе и для понимания. Работа с битами это вообще ИМХО слабая сторона Си.
А, я подумал Вы про мой код Ну побитово конечно дольше будет. Только тут и асм не особо спасает. Все-равно с масками эффективнее работать. Тут причина кроется в устройстве самого процессора - операции над регистрами атомарные, а посему работа с группой битов быстрее, чем последовательно каждый. BSF и BSR в данной задаче не помогут. В общем, быстрее не получится.
конечно. так и там и там с масками в итоге. просто не понятно желание автора книжки делать маску 00000000100000000 и проверять по 1 биту - ИМХО этим он всех путает, в том числе и себя
быстрее наверное нельзя... Действительно, тут ни bsr, ни таблицы не помогут... Однако и задачи такие редко бывают...
