сабж.
как узнать номер n-го установленного (1) бита внутри long?
не ли какой-либо команды процессора или какой-нибудь код для С/С++

Здравствуйте, ilnar, Вы писали:

I>сабж.
I>как узнать номер n-го установленного (1) бита внутри long?
I>не ли какой-либо команды процессора или какой-нибудь код для С/С++

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

unsigned long temp = 0;

for (int i = 0; i< 32; i++)
{
    // проверяешь установлен ли i-й бит в 1...
    if ((your_long & temp) >> i) == 1)
    {
        // какая то обработка...
    }

    //переходим к след биту
    temp = temp << 1;
}

Здравствуйте, ilnar, Вы писали:

I>как узнать номер n-го установленного (1) бита внутри long?
I>не ли какой-либо команды процессора или какой-нибудь код для С/С++

Такой команды нет. Но написать функцию или макрос несложно.

за O(N)

int what_bit(unsigned long x)
{
  if(x==0) return -1; // no bits
  int c=0;
  while(!(x&1)) { x>>=1; ++c; }
  if(x!=1) return -2; // multiple bits
  return c;
}

За O(log N) — двоичный поиск: x<>2^16? x<>2^8? и так далее.

#define bit(n) (1<<(n))

int what_bit(unsigned long x)
{
  if(x == 0) return -1;
  if((x & (x-1)) != 0) return -2; // выставлено более 1 бита

#define test(n) if(x == bit(n)) return n; else if(x < bit(n))

  // 0..31
  test(16)
    // 0..15
    test(8)
      // 0..7
      test(4)
        // 0..3
        test(2)
          // 0..1
          test(1)
            return 0;
          else
            return -3; // ошибка! так не бывает.
        else
          return 3;
      else
        // 4..6
        test(5)
          return 4;
        else
          return 6;
    else
      // 9..15
      test(12)
        // 9..11
        test(10)
          return 9;
        else
          return 11;
      else
        // 13..15
        test(14);
          return 13;
        else
          return 15;
  else
    // 17..31
    test(24)
      // 17..23
      test(20)
        // 17..19
        test(18)
          return 17;
        else
          return 19;
      else
        // 21..23
        test(22)
          return 21;
        else
          return 23;
    else
      // 25..31
      test(28)
        // 25..27
        test(26)
          return 25;
        else
          return 27;
      else
        // 29..31
        test(30)
          return 29;
        else
          return 31;

#undef test
}

Здравствуйте, Кодт, Вы писали:

К>за O(N)

[]

К>За O(log N) — двоичный поиск: x<>2^16? x<>2^8? и так далее.

[]

Я видел код (буквально пять строчек), который это делает без цикла за O(1). Вот только ссылку никак не могу найти

Здравствуйте, MaximE, Вы писали:

ME>Я видел код (буквально пять строчек), который это делает без цикла за O(1). Вот только ссылку никак не могу найти

int what_bit(unsigned long x)
{
  if(x==0) return -1; // no bits
  if (x & (x-1)) return -2; // multiple bits

  return int(log(x)/log(2)); //  :shuffle: ;) 
}

Как бы логарифм по основанию два извлечь без плавающей точки и за О(1)?

Здравствуйте, Sergeem, Вы писали:

S>Как бы логарифм по основанию два извлечь без плавающей точки и за О(1)?

Промелькнула такая мысль: поиграться с непереносимостью Можно преобразовать число в плавающую точку и поиграться с битами, ведь если наше число — степень двойки, то результат получится с мантиссой 1 и нужным порядком.

Здравствуйте, ilnar, Вы писали:

I>сабж.
I>как узнать номер n-го установленного (1) бита внутри long?
I>не ли какой-либо команды процессора или какой-нибудь код для С/С++

char GetBitPos( long n )
{
   char pos = 0;
   if(n & 0xFFFF0000) pos = 16, n >>= 16;
   if(n & 0x0000FF00) pos += 8, n >>= 8;
   if(n & 0x000000F0) pos += 4, n >>= 4;
   if(n & 0x0000000C) pos += 2, n >>= 2;
   if(n & 0x00000002) pos += 1;
   return pos;
};

Здравствуйте, ilnar, Вы писали:

I>сабж.
I>как узнать номер n-го установленного (1) бита внутри long?
I>не ли какой-либо команды процессора или какой-нибудь код для С/С++

Для i486+

int BitPos(long n)
{
    __asm
    {
      mov eax, n
      bsf eax, eax
    }
}

Здравствуйте, UgN, Вы писали:

UgN>char GetBitPos( long n )

(риторический вопрос) А не дожен ли прототип функции быть таким? :

char GetBitPos( lond tested, long n )

Здравствуйте, WeCom, Вы писали:

WC>

UgN>char GetBitPos( long n )
WC>

WC>(риторический вопрос) А не дожен ли прототип функции быть таким? :
WC>

WC>char GetBitPos( lond tested, long n )
WC>

Что это значит?

Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, WeCom, Вы писали:

WC>

UgN>char GetBitPos( long n )
WC>

WC>(риторический вопрос) А не дожен ли прототип функции быть таким? :
WC>

WC>char GetBitPos( lond tested, long n )
WC>

UgN>Что это значит?
UgN>
Что сказано в сабже? — "как узнать номер n-го установленного (1) бита внутри long?"
Т.е. есть какое-то число (long). У него установлено несколько битов (в 1). Надо узнать номер (позицию) энного. Для n=1, задача в нахождении позиции самого правого единичного бита, для n=2 — позиции следующего единичного после самого правого, и т.д. А вы какую задачу решаете? — Найти позицию единственного единичного бита в long'е? Так это другая задача.

Здравствуйте, WeCom, Вы писали:

WC>(риторический вопрос) А не дожен ли прототип функции быть таким? :

char GetBitPos( lond tested, long n )

Вообще то верно...
Вот, например, так ( для intel 80486+ ) :

char GetBitPos(long tested, long n)
{
  long i;
  char pos;
  for(i = 0; i < tested, n != 0; i++)
  {
    __asm
    {
       bsf eax, n
       btr n, eax
       mov pos, al
    }
  }
  return i == tested ? pos : -1;
}

Здравствуйте, WeCom, Вы писали:

WC>А вы какую задачу решаете? — Найти позицию единственного единичного бита в long'е?
Тут я не прав, хотя в любом случае решаете какую-то другую (не из сабжа) задачу

Здравствуйте, WeCom, Вы писали:

WC>Что сказано в сабже? — "как узнать номер n-го установленного (1) бита внутри long?"
WC>Т.е. есть какое-то число (long). У него установлено несколько битов (в 1). Надо узнать номер (позицию) энного. Для n=1, задача в нахождении позиции самого правого единичного бита, для n=2 — позиции следующего единичного после самого правого, и т.д. А вы какую задачу решаете? — Найти позицию единственного единичного бита в long'е? Так это другая задача.

Ooops!

Здравствуйте, Dmitry Kukushkin, Вы писали:

DK>Вот, например, так ( для intel 80486+ ) :

DK>

DK>char GetBitPos(long tested, long n)
DK>{
DK>  long i;
DK>  char pos;
DK>  for(i = 0; i < tested, n != 0; i++)
DK>  {
DK>    __asm
DK>    {
DK>       bsf eax, n
DK>       btr n, eax
DK>       mov pos, al
DK>    }
DK>  }
DK>  return i == tested ? pos : -1;
DK>}
DK>

Неверно. Например, GetBitPos(0xF,3) должен вернуть 2, а возвращает -1. Возможно, n и tested перепутаны местами, но GetBitPos(3,0xF) также возвращает -1.

Здравствуйте, WeCom, Вы писали:

WC>Неверно. Например, GetBitPos(0xF,3) должен вернуть 2, а возвращает -1. Возможно, n и tested перепутаны местами, но GetBitPos(3,0xF) также возвращает -1.


Извиняюсь...
Аргументы действительно перепутаны и в цикле там малек не то...
Ну вот — для ясности:

char GetBitPos(long data, long n)
{
  int i;
  char pos;
  for(i = 0; i < n && data != 0; i++)
  {
    __asm
    {
       bsf eax, data
       btr data, eax
       mov pos, al
    }
  }
  return i == n ? pos : -1;
}

Здравствуйте, Sergeem, Вы писали:

S>Как бы логарифм по основанию два извлечь без плавающей точки и за О(1)?

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

int what_bit (long number)
{
  float f1;
  int f2;

  _asm
  {
    fld1
    fild dword ptr [number]
    fyl2x
    fst dword ptr [f1]
    fistp word ptr [f2]
  }
  
  if (f1==f2) return f2
  
  return -1;
}

Может, конечно, где и накосячил , но общая идея такая...

Здравствуйте, MaximE, Вы писали:

ME>Я видел код (буквально пять строчек), который это делает без цикла за O(1). Вот только ссылку никак не могу найти

Оказалось, что не за O(1):

http://www.akzhan.midi.ru/devcorner/articles/bit-manipulation.html

А чем приведенный код поможет вопрошающему?
Насколько скудные познания ассемблера мне позовляют судить, в eax после выполнения данной последовательности команд будет помещен номер крайнего справа установленного в (1) бита (т.е. первого установленного бита, ежели такой есть). В вопросе же сказано — нужен номер n-го установленного бита. В этом случае я вижу 2 варианта — либо просто тупой перебор со свигом маски и счетчиком, либо использование более "быстрого" способа с BitPos, счетчиком и сдвигом результата.

I>сабж.
I>как узнать номер n-го установленного (1) бита внутри long?
I>не ли какой-либо команды процессора или какой-нибудь код для С/С++

DK>Для i486+

DK>

DK>int BitPos(long n)
DK>{
DK>    __asm
DK>    {
DK>      mov eax, n
DK>      bsf eax, eax
DK>    }
DK>}
DK>

Здравствуйте, Baggy, Вы писали:

B>Здравствуйте, ilnar, Вы писали:

I>сабж.
I>как узнать номер n-го установленного (1) бита внутри long?
I>не ли какой-либо команды процессора или какой-нибудь код для С/С++

B>я бы организовал цикл по маске выделения,
B>что то в духе

B>

B>unsigned long temp = 0;

B>for (int i = 0; i< 32; i++)
B>{
B>    // проверяешь установлен ли i-й бит в 1...
B>    if ((your_long & temp) >> i) == 1)
B>    {
B>        // какая то обработка...
B>    }

B>    //переходим к след биту
B>    temp = temp << 1;
B>}
B>

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