очистить все, кроме двух самых значимых битов в слове - PullRequest
Новая
       27

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

2 голосов
/ 20 июля 2010

Учитывая 32-битное целое число, в котором, как известно, установлено как минимум 2 бита, есть ли способ эффективно очистить все, кроме 2 старших значащих битов?т.е. я хочу убедиться, что на выходе установлено ровно 2 бита.

Что если на входе гарантированно установлены только 2 или 3 бита ??

Примеры: 

0x2040 -> 0x2040
0x0300 -> 0x0300
0x0109 -> 0x0108
0x5040 -> 0x5000

Результаты сравнительного анализа:

Код: 

QueryPerformanceFrequency(&freq);
/***********/
value = (base =2)|1;
QueryPerformanceCounter(&start);
for (l=0;l<A_LOT; l++)
{
  //!!value calculation goes here
  junk+=value;    //use result to prevent optimizer removing it.

  //advance to the next 2|3 bit word
  if (value&0x80000000)
  {  if (base&0x80000000)
     {  base=6;
     }
     base*=2;
     value=base|1;
  }
  else
  {  value<<=1;
  }
}
QueryPerformanceCounter(&end);
time = (end.QuadPart - start.QuadPart);
time /= freq.QuadPart;
printf("--------- name\n");
printf("%ld loops took %f sec (%f additional)\n",A_LOT, time, time-baseline);
printf("words /sec = %f Million\n",A_LOT/(time-baseline)/1.0e6);

Результаты использования настроек выпуска VS2005 по умолчанию на Core2Duo E7500@2,93 ГГц: 

--------- BASELINE
1000000 loops took 0.001630 sec
--------- sirgedas
1000000 loops took 0.002479 sec (0.000849 additional)
words /sec = 1178.074206 Million
--------- ashelly
1000000 loops took 0.004640 sec (0.003010 additional)
words /sec = 332.230369 Million
--------- mvds
1000000 loops took 0.005250 sec (0.003620 additional)
words /sec = 276.242030 Million
--------- spender
1000000 loops took 0.009594 sec (0.007964 additional)
words /sec = 125.566361 Million
--------- schnaader
1000000 loops took 0.025680 sec (0.024050 additional)
words /sec = 41.580158 Million

Ответы [ 10 ]

8 голосов
/ 20 июля 2010

Если входные данные гарантированно имеют ровно 2 или 3 бита, то ответ может быть вычислен очень быстро.Мы используем тот факт, что выражение x & (x-1) равно x с очищенным LSB.Применение этого выражения дважды ко входу даст 0, если установлено 2 или менее бит.Если установлено ровно 2 бита, мы возвращаем исходный ввод.В противном случае мы возвращаем исходный ввод с очищенным LSB.

Вот код на C ++: 

// assumes a has exactly 2 or 3 bits set
int topTwoBitsOf( int a ) 
{
   int b = a&(a-1);         // b = a with LSB cleared
   return b&(b-1) ? b : a;  // check if clearing the LSB of b produces 0
}

Это может быть записано как одно запутанное выражение, если вам нравится: 

int topTwoBitsOf( int a )
{
   return a&(a-1)&((a&(a-1))-1) ? a&(a-1) : a;
}
4 голосов
/ 20 июля 2010

Я бы создал маску в цикле.В начале маска равна 0. Затем перейдите от MSB к LSB и установите каждый соответствующий бит в маске на 1, пока не найдете 2 установленных бита.И, наконец, значение И с этой маской. 

#include <stdio.h>
#include <stdlib.h>

int clear_bits(int value) {

  unsigned int mask = 0;
  unsigned int act_bit = 0x80000000;
  unsigned int bit_set_count = 0;

  do {
    if ((value & act_bit) == act_bit) bit_set_count++;
    mask = mask | act_bit;
    act_bit >>= 1;
  } while ((act_bit != 0) && (bit_set_count < 2));

  return (value & mask);
}

int main() {
  printf("0x2040 => %X\n", clear_bits(0x2040));
  printf("0x0300 => %X\n", clear_bits(0x0300));
  printf("0x0109 => %X\n", clear_bits(0x0109));
  printf("0x5040 => %X\n", clear_bits(0x5040));
  return 0;
}

Это довольно сложно, но должно быть более эффективным, так как каждый раз используется цикл for для 32 битов (и очищать все биты, кроме двух наиболее значимых установленных битов).).В любом случае, обязательно сравните тесты различными способами, прежде чем использовать один из них.

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

1 голос
/ 20 июля 2010

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

#include <stdio.h>
unsigned char bittable1[256];
unsigned char bittable2[256];

unsigned int lookup(unsigned int);
void gentable(void);

int main(int argc,char**argv)
{
    unsigned int challenge = 0x42341223, result;
    gentable();

    if ( argc > 1 ) challenge = atoi(argv[1]);

    result = lookup(challenge);

    printf("%08x --> %08x\n",challenge,result);
}

unsigned int lookup(unsigned int i)
{
    unsigned int ret;

    ret = bittable2[i>>24]<<24; if ( ret ) return ret;
    ret = bittable1[i>>24]<<24;
    if ( !ret )
    {
            ret = bittable2[i>>16]<<16; if ( ret ) return ret;
            ret = bittable1[i>>16]<<16;
            if ( !ret )
            {
                    ret = bittable2[i>>8]<<8; if ( ret ) return ret;
                    ret = bittable1[i>>8]<<8;
                    if ( !ret )
                    {
                            return bittable2[i] | bittable1[i];
                    } else {
                            return (ret | bittable1[i&0xff]);
                    }
            } else {
                    if ( bittable1[(i>>8)&0xff] )
                    {
                            return (ret | (bittable1[(i>>8)&0xff]<<8));
                    } else {
                            return (ret | bittable1[i&0xff]);
                    }
            }
    } else {
            if ( bittable1[(i>>16)&0xff] )
            {
                    return (ret | (bittable1[(i>>16)&0xff]<<16));
            } else if ( bittable1[(i>>8)&0xff] ) {
                    return (ret | (bittable1[(i>>8)&0xff]<<8));
            } else {
                    return (ret | (bittable1[i&0xff]));
            }
    }
}

void gentable()
{
    int i;
    for ( i=0; i<256; i++ )
    {
            int bitset = 0;
            int j;
            for ( j=128; j; j>>=1 )
            {
                    if ( i&j )
                    {
                            bitset++;
                            if ( bitset == 1 ) bittable1[i] = i&(~(j-1));
                            else if ( bitset == 2 ) bittable2[i] = i&(~(j-1));
                    }
            }
            //printf("%3d %02x %02x\n",i,bittable1[i],bittable2[i]);
    }
}
1 голос
/ 20 июля 2010

Вот еще одна попытка (без циклов, без поиска, без условных выражений).На этот раз это работает: 

var orig=0x109;
var x=orig;
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
x = orig & ~(x & ~(x >> 1));
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
var solution=orig & ~(x >> 1);
Console.WriteLine(solution.ToString("X")); //0x108

Возможно, кто-то умнее меня укоротит.

1 голос
/ 20 июля 2010

сколько памяти доступно при какой задержке?Я бы предложил таблицу поиска; -)

, но серьезно: если вы выполняете это на 100-х числах, вам может понадобиться 8-битная таблица поиска, дающая 2 мсек, и еще одна 8-битная таблица поиска, дающая 1 мсек.,В зависимости от процессора, это может побить действительно считающий бит.

Для скорости я бы создал таблицу соответствия, отображающую входной байт в

M (I) = 0, если установлен 1 или 0 бит

M (I) = B 'в противном случае, где B' - это значение B с установленными битами в 2 мсек.

32-разрядный тип int - это 4 входных байта I1 I2 I3 I4.
Lookup M (I1), если ненулевое значение, все готово.
Сравнить M (I1) == 0, если ноль, повторить предыдущий шаг для I2.
Иначе, поиск I2 во второй таблице поиска с 1Биты MSB, если ненулевой, все готово.Иначе, повторите предыдущий шаг для I3.

и т. Д. И т. Д. На самом деле ничего не зацикливайте на I1-4, а разверните его полностью.

Суммирование: 2 таблицы поиска с 256 записями, 247 /256 случаев разрешаются одним поиском, примерно 8/256 - двумя поисками и т. Д.

редактировать: таблицы для ясности (входные данные, таблица битов 2 MSB, таблица битов 1 MSB) 

  I    table2    table1
  0  00000000  00000000
  1  00000000  00000001
  2  00000000  00000010
  3  00000011  00000010
  4  00000000  00000100
  5  00000101  00000100
  6  00000110  00000100
  7  00000110  00000100
  8  00000000  00001000
  9  00001001  00001000
 10  00001010  00001000
 11  00001010  00001000
 12  00001100  00001000
 13  00001100  00001000
 14  00001100  00001000
 15  00001100  00001000
 16  00000000  00010000
 17  00010001  00010000
 18  00010010  00010000
 19  00010010  00010000
 20  00010100  00010000
 ..
250  11000000  10000000
251  11000000  10000000
252  11000000  10000000
253  11000000  10000000
254  11000000  10000000
255  11000000  10000000
0 голосов
/ 21 июля 2010

Мое решение:

Используйте «Лучший метод для подсчета битов в 32-разрядном целом числе» , затем сбросьте младший бит, если ответ равен 3. Работает только тогда, когда ввод ограничен 2 или 3 установленными битами. 

unsigned int c; // c is the total bits set in v
unsigned int v = value;
v = v - ((v >> 1) & 0x55555555);                    
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

crc+=value&value-(c-2);
0 голосов
/ 20 июля 2010

Вот моя реализация в C # 

uint OnlyMostSignificant(uint value, int count) {
    uint newValue = 0;
    int c = 0;

    for(uint high = 0x80000000; high != 0 && c < count; high >>= 1) {
        if ((value & high) != 0) {
            newValue = newValue | high;
            c++;
        }
    }

    return newValue;
}

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

0 голосов
/ 20 июля 2010

Я бы также использовал подход, основанный на таблицах, но я считаю, что одной таблицы достаточно. Возьмите 4-битный регистр в качестве примера. Если ваш ввод гарантированно имеет 2 или 3 бита, то ваш вывод может быть только одним из 6 значений 

      0011
      0101
      0110
      1001
      1010
      1100

Поместите эти возможные значения в массив, отсортированный по размеру. Начиная с наибольшего, найдите первое значение, которое равно или меньше целевого значения. Это твой ответ. Для 8-битной версии у вас будет больше возможных возвращаемых значений, но все равно легко меньше максимально возможных перестановок 8 * 7. 

public static final int [] MASKS = {
        0x03, //0011
        0x05, //0101
        0x06, //0110
        0x09, //1001
        0x0A, //1010
        0x0C, //1100
};


    for (int i = 0; i < 16; ++i) {
        if (countBits(i) < 2) {
            continue;
        }
        for (int j = MASKS.length - 1; j >= 0; --j) {
            if (MASKS[j] <= i) {
                System.out.println(Integer.toBinaryString(i) + " " + Integer.toBinaryString(MASKS[j]));
                break;
            }
        }
    }
0 голосов
/ 20 июля 2010

Вот какой-то питон, который должен работать: 

def bit_play(num):
    bits_set = 0
    upper_mask = 0
    bit_index = 31
    while bit_index >= 0:
        upper_mask |= (1 << bit_index)
        if num & (1 << bit_index) != 0:
            bits_set += 1
            if bits_set == 2:
                num &= upper_mask
                break
        bit_index -= 1
    return num

Это делает один проход по номеру. Он строит маску битов, которые он пересекает, поэтому он может маскировать нижние биты, как только достигнет второго по значимости. Как только он находит второй бит, он начинает очищать младшие биты. Вы должны иметь возможность создать маску из старших битов и &= вместо второй цикла while. Может быть, я взломаю это и отредактирую сообщение.

0 голосов
/ 20 июля 2010

Используя вариант этого , я придумал следующее: 

var orig=56;
var x=orig;
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
Console.WriteLine(orig&~(x>>2));

В c #, но должен легко переводиться.

РЕДАКТИРОВАТЬ

Я не уверен, что ответил на ваш вопрос.Это берет старший бит и сохраняет его и бит рядом с ним, например.101 => 100

...