代码之家 › 专栏 › 技术社区 › AShelly

清除字中除两个最高有效位以外的所有设置位

bit-manipulation language-agnostic algorithm

AShelly · 技术社区 · 14 年前

如果保证输入只有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);

在Core2Duo上使用VS2005默认版本设置的结果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 回复 | 直到 14 年前

Tom Sirgedas 14 年前

如果保证输入正好有2或3位,那么答案可以很快计算出来。我们利用表达式x&(x-1)等于清除LSB后的x。如果设置了2个或更少的位,则对输入应用该表达式两次将产生0。如果正好设置了2位,则返回原始输入。否则,我们返回LSB被清除的原始输入。

// 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;
}

schnaader 14 年前

我会在一个循环中创建一个面具。开始时,掩码为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;
}

当然,如果内存不是问题的话,可以使用一些推荐的查找表方法—这会快得多。

mvds 14 年前

但说真的:如果要对100个数字执行此操作,则只需要一个8位查找表提供2 msb,另一个8位查找表提供1 msb。根据处理器的不同,这可能会超过真正的计数位。

如果设置了1或0位,M(I)=0

M(I)=B'否则,其中B'是设置了2个msb位的B的值。

32位int是4个输入字节I1 I2 I3 I4。
查找M(I1),如果不为零,则完成。
比较M(I1)==0,如果为0,则对I2重复上一步。
否则,对I3重复上一步。

总结: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

spender 14 年前

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

mvds 14 年前

#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]);
    }
}

spender 14 年前

使用变量 this ,我得出如下结论:

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));

编辑

我不太确定我是否回答了你的问题。这将获取最高的位并保留它和它旁边的位,例如101=>100

D.Shawley 14 年前

下面是一些可以工作的python:

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

它使一个人越过这个数字。它构建了一个交叉位的掩码,这样一旦到达第二个最重要的位,它就可以屏蔽掉底部的位。 ~~一旦找到第二位,它就开始清除低位。您应该能够创建一个包含高位和高位的掩码 &=~~

Jherico 14 年前

我也会使用基于表的方法,但我相信一个表就足够了。以4位为例。如果您的输入保证有2或3位,那么您的输出只能是6个值中的一个

将这些可能的值放入按大小排序的数组中。从最大值开始,找到第一个等于或小于目标值的值。这是你的答案。对于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;
            }
        }
    }

Vincent McNabb 14 年前

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;
}

AShelly 14 年前

使用 "The best method for counting bits in a 32-bit integer" ,如果答案是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);