位操作问题，算法高手请进

举个例子 ：


例如一个数组有4个字节

二进制为

00000000 00000000 00000000 00000000 


从任意一个位开始 ， 到任意一个位结束， 把中间的全部位设置为1 ， 求最快方法，优美的~~

例如从 4 位开始 ，21位结束，要求结果为


00001111 11111111 11111111 10000000

高手帮我啊~

120 个解决方案

#1

&ffffffff
//一共就那么多种情况,先存好,直接取出来&一下就OK了.

#2

是 |不是&.

#3

引用 1 楼 lthyxy 的回复:

&ffffffff
//一共就那么多种情况,先存好,直接取出来&一下就OK了.

情况不是很多，但也不是很少~~~~

主要分几类

右边的 11100000

左边的 00000111

中间的 00111000


如果从 3 位开始 6 位结束

你就要取 00011100

怎么判断要取 00011100这个去与呢

思路简单，代码难写（ 我的水平有限)

#4

我的做法就是用bitset的容器 先从起始位开始 取反  再从结束位开始取反 调用库函数

#5

其实代码我已经写出来

但极其恶心~ 效率也低~~

求个优美代码~

#6

顶楼上的说法  直接用bitset的set和reset函 解决，很简单。效率也很高！

#7

引用 4 楼 hnuqinhuan 的回复:

我的做法就是用bitset的容器 先从起始位开始 取反 再从结束位开始取反 调用库函数

这个不行~  其他位可能已经被人置1，这种方法破后了原有的信息了

#8

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
	bitset<32> bitvec;
	int pos1,pos2;
	cin >> pos1 >> pos2;
	for(int i = pos1;i <= pos2;i ++ )
		bitvec.set(i);
	cout << bitvec << endl;
	return 0;
}

#9

引用 8 楼 hnuqinhuan 的回复:

C/C++ code

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
    bitset<32> bitvec;
    int pos1,pos2;
    cin >> pos1 >> pos2;
    for(int i = pos1;i <= pos2;i ++……

本来我是不想要库了，不过你也提醒我了，我去看看bitset的代码看看怎么实现的

#10

8楼已经达到这个效果了.

#11

for(int i = pos1;i <= pos2;i ++ )
        bitvec.set(i);



不过这句效率应该不高

bitset是一位一位的设置为1

应该能利用我从某位开始某位结束这个特殊的条件进行优化

#12

lthyxy  的方法能利用这个条件，但代码不好写~~ 那个高手能实现一下~

#13

unsigned long lNum = 0;
lNum |= 0x0FFFFF80;

#14

看了一看bitset的代码，好像也是一位一位设置的，看来是性能极限哦。

求高手

#15

引用 14 楼 r11222 的回复:

看了一看bitset的代码，好像也是一位一位设置的，看来是性能极限哦。

求高手

不会吧，应该很快了。难道还有更快的招？

#16

只能一位一位的，我给你写一个C实现吧，用库总归不好说事。

#17

#define BitSet（from,to） (((1<<((to)-(from)))-1)<<(from))
思路就是这样，具体从左数还是从右数可以再调整，类型转换也要加上

#18

你举的两个例子是矛盾的，先搞清楚你自己的需求再说：

例如从 4 位开始 ，21位结束，要求结果为
00001111 11111111 11111111 10000000
这个感觉是从5位开始，连续21位

如果从 3 位开始 6 位结束
你就要取 00011100
这个又是4位开始6位结束。

#19

与0FFFFF80相与

#20

f0 ff 3f 0 请按任意键继续. . .

#include <iostream>
using namespace std;

void setBits(unsigned char *buffer,int begin,int end)
{
	while(begin<=end)
	{
		buffer[begin/8]|=1<<(begin%8);
		++begin;
	}
}

int main()
{
	unsigned char buffer[4]={0};
	setBits(buffer,4,21);

	for(int i=0;i<4;++i)
	{
		cout<<hex<<(int)buffer[i]<<" ";
	}

	return 0;
}

二进制会看吧，要颠倒每个字节的高低4位才真正是从低地址往高地址的二进制状态。

f0 ff 3f 0 颠倒成： 0f ff f3 0

#21

int set_bit3(int testdata,int min,int max)  //testdata为要处理的数据  
{                                              //min为开始置1的位  max为末尾

for(int n=min;n<=max;n++)
testdata|=(1<<n);
return testdata;
}
这是我自己编的处理置1的函数 你可以拿去试一试

#22

引用 20 楼 qq120848369 的回复:

C/C++ code
f0 ff 3f 0 请按任意键继续. . .

C/C++ code
#include <iostream>
using namespace std;

void setBits(unsigned char *buffer,int begin,int end)
{
    while(begin<=end)
    {
        buffer[begin/8]……

我用unsigned char的原因是cout<<hex<<(int)buffer[i]<<" ";的时候int转型会造成高位填充符号位,所以我用unsigned char，防止影响打印结果的简洁性。

#23

我也来凑凑热闹：）

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
	unsigned int number;
	unsigned int bnumber;
	int start, end;
	int onedigits;
	cin >> start >> end;

	onedigits = end - start + 1;

	number = 0xffffffff;
	number = number << (31 - end);
	printf("%0x\n", number);

	bnumber = 0xffffffff;
	bnumber = bnumber >> start;
	printf("%0x\n", bnumber);

	number = number & bnumber;
	printf("%8x\n", number);
}

#24

23L用了2次移位，和1次位与运算。没有循环。

#25

去掉了23L没用到2行代码：

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
	unsigned int number;
	unsigned int bnumber;
	int start, end;

	cin >> start >> end;

	number = 0xffffffff;
	number = number << (31 - end);		// 把从end到最后的各位全部变成0
	printf("%0x\n", number);

	bnumber = 0xffffffff;
	bnumber = bnumber >> start;		    // 把前start位变成0
	printf("%0x\n", bnumber);

	number = number & bnumber;			// 把number和bnumber位与，应该就是楼主要的结果
	printf("%8x\n", number);
}

#26

引用 25 楼 pathuang68 的回复:

去掉了23L没用到2行代码：
C/C++ code

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    unsigned int number;
    unsigned int bnumber;
    int start, end;

    cin >> start >> e……

楼主要char数组的。。。。

#27

char数组不是问题
char a[4];
unsigned int &b = *(unsigned int*)a

#28

随便写的，看看行不

unsigned long foo(int f, int r)
{
   assert(f>=0 && f<32 && r>=0 && r<32 && f<=r);
   return (unsigned long(-1) >> (31-r)) & (-1 << (f));
}

cout << bitset<32>(foo( 0, 31)) << endl;
cout << bitset<32>(foo( 0,  0)) << endl;
cout << bitset<32>(foo( 1, 30)) << endl;
cout << bitset<32>(foo(31, 31)) << endl;

#29

引用 26 楼 qq120848369 的回复:

引用 25 楼 pathuang68 的回复:

去掉了23L没用到2行代码：
C/C++ code

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
unsigned int number;
unsigned int bnumber;
int start, end;……

如果不是非要用char数组的话，25L的速度应该是非常非常快了(不敢说最快，看后面的高手还有没有更厉害的招数)

不过如果一定要用char数组的话，怎么也优雅不起来啊。

#30

引用楼主 r11222 的回复:

举个例子 ：


例如一个数组有4个字节

二进制为

00000000 00000000 00000000 00000000 


从任意一个位开始 ， 到任意一个位结束， 把中间的全部位设置为1 ， 求最快方法，优美的~~

例如从 4 位开始 ，21位结束，要求结果为


00001111 11111111 11111111 10000000

高手帮我啊~……

按你的理解是不是
从  4 位开始 ，24位结束，要求结果为


00001111 11111111 11111111 10000000
int main()
{
    unsigned int a = 0;
    printf("%x\n", set(a, 4, 21));
    return 0;
}

unsigned set(unsigned arr, int l, int r)
{
    return arr | ((((0xffffffff) >> (31-r+l))) << (31-r));
}

#31

int main()
{
  unsigned int a = 0;
  printf("%x\n", set(a, 4, 21));
  return 0;
}

unsigned set(unsigned arr, int l, int r)
{
  return arr | ((((0xffffffff) >> (31-r+l))) << (31-r));
}

#32

如果楼主的数组正好4个字节，如果楼主的处理器恰好又是32位的，那么……  请参考31楼！

#33

我以前还遇到过更变态的事情，做bit矩阵填充http://topic.csdn.net/u/20090412/10/087c520a-38b4-441c-9b5a-2c8d38551105.html

#34

引用 6 楼 yweige2010 的回复:

顶楼上的说法 直接用bitset的set和reset函 解决，很简单。效率也很高！

++1

#35

(0xffffffffUL >> high) & (0xffffffffUL << low)

#36

诸位讨论的都不在点上,楼主要的是char数组，楼主说4字节，你们就凑活4字节，如果要1000个字节的，还不是要满足通用性的实现么。

#37

value |= (0xffffffffUL >> high) & (0xffffffffUL << low)

#38

引用 36 楼 qq120848369 的回复:

诸位讨论的都不在点上,楼主要的是char数组，楼主说4字节，你们就凑活4字节，如果要1000个字节的，还不是要满足通用性的实现么。

如果是任意大小的char数组，起始与结束可以用位移运算，中间部分memset

#39

引用 38 楼 sbwwkmyd 的回复:

引用 36 楼 qq120848369 的回复:
诸位讨论的都不在点上,楼主要的是char数组，楼主说4字节，你们就凑活4字节，如果要1000个字节的，还不是要满足通用性的实现么。

如果是任意大小的char数组，起始与结束可以用位移运算，中间部分memset

写一个出来看看，你就知道数组和int的差别了，假设就9个字节吧。

#40

引用 39 楼 qq120848369 的回复:

写一个出来看看，你就知道数组和int的差别了，假设就9个字节吧。

啊？太难了！不会写，怎么办啊？
还是你先写一个吧，我好学习学习啊

#41

std::bitset<>
boost::bitset<>

#42

引用 40 楼 sbwwkmyd 的回复:

引用 39 楼 qq120848369 的回复:
写一个出来看看，你就知道数组和int的差别了，假设就9个字节吧。
啊？太难了！不会写，怎么办啊？
还是你先写一个吧，我好学习学习啊

看26楼。

#43

如果仅仅是四个字节，就好做了，直接强制类型转换为 unsigned int 处理。

1 . 下标变换   ，把从左边开始的下标变换成从右边开始的下标 ，设原下标为 begin ，end
    则 i = 32-begin; j= 32-end;

2 . 得到一个从i位起之后全是1的数，方法为： tmp1=(1<<i)-1;

3.  得到一个从j位起之后全是1的数， 方法为:   tmp2=(1<<j)-1;

4.  tmp1-tmp2 即是最终结果，即： result=tmp1-tmp2 =（1<<i）-(1<<j);

unsinged int change(int begin, int end)
{
        int  i = 32-begin;
        int  j = 32-end;
       
        return (1<<i)-(1<<j);


}

#44

如果是任意长度的数组：

void setBits(unsigned char *buffer,int begin,int end)
{
    stactic const char hash[8]={0xff, 0x7f, 0x3f, 0x1f, 0xf, 0x7, 0x3, 0x1};

    for(int i=1+begin/8; i<end/8; ++i)        //处理数组中间
           buffer[i] |= hash[0];
    if (begin/8 == end/8)                   //处理边界
    {
         buffer[begin/8] |= hash[begin%8]-hash[end%8];    //如果两个边界在一个数组元素中
 
    }
    else                                            //如果数组边界在两个不同元素中
    {
        buffer[begin/8] |= hash[begin%8];
        buffer[begin/8] |= (~hash[end%8]);

    }

}

#45

引用 42 楼 qq120848369 的回复:

引用 40 楼 sbwwkmyd 的回复:

引用 39 楼 qq120848369 的回复:
写一个出来看看，你就知道数组和int的差别了，假设就9个字节吧。
啊？太难了！不会写，怎么办啊？
还是你先写一个吧，我好学习学习啊


看26楼。

观摩了20的代码，确实简洁，这样的代码我都是用做DEBUG版本校验RELEASE版本正确性的副本。
写了一个memset字节对齐的版本，要更高效可以改写成CPU字对齐的版本。

void setBits(byte *buffer, uint32 begin, uint32 count)
{
	assert(buffer != NULL && count != 0);
	uint32 index = begin, left = 0xff, right = 0xff;
	begin &= 7;//起始位偏移
	index >>= 3;//起始字节偏移
	count += begin;//结束位
	buffer += index;//起始字节
	left <<= begin;//起始字节值
	index = count;
	count &= 7;//结束位偏移
	count ^= 7;//位偏量 = 8 - 结束位偏移
	++count;
	right >>= count;//结束字节值
	if((index >>= 3) == 0) *buffer |= (byte)(left & right);//起始字节与结束字节相同
	else
	{
		*(buffer + index) |= (byte)right;
		*buffer |= (byte)left;
		--index;
		++buffer;
		memset(buffer, 0xff, index);
	}
}

#46

这个问题可以转变为大数减法来处理可以提高算法的效率

设

B 为赋值开始的bit位位置
E 为赋值结束的bit位位置
B必须大于E

N 为 2的X位的大数（X为8的整数倍）

结果始终等于

2^(B+1) - 2^(E+1)

由此，可以简化赋值操作为
bitset<N> a;
bitset<N> b;

a.set(B+1);
b.set(E+1);

下面的大数减法我就不在说明了.

#47

inline unsigned long get_mask( int begin, int end ) 
{
  return ( (1 << end) - 1 ) ^ ( (1 << begin) - 1 );
}

#48

引用 45 楼 sbwwkmyd 的回复:

引用 42 楼 qq120848369 的回复:
引用 40 楼 sbwwkmyd 的回复:

引用 39 楼 qq120848369 的回复:
写一个出来看看，你就知道数组和int的差别了，假设就9个字节吧。
啊？太难了！不会写，怎么办啊？
还是你先写一个吧，我好学习学习啊


看26楼。

观摩了20的代码，确实简洁，这样的代码我都是用做DEBUG版本校验RELEASE……

#include <iostream>
#include <cstring>
using namespace std;

void setBits(unsigned char *buffer,int begin,int end)
{
	unsigned char *pBeg=&buffer[begin/8];
	unsigned char *pEnd=&buffer[end/8];

	memset(pBeg,-1,pEnd-pBeg+1);	//全部置1

	*pBeg&=(-1)<<(begin%8);	/*置反*/
	*pEnd^=(-1)<<(end%8+1);
}

int main()
{
	unsigned char buffer[4]={0};

	setBits(buffer,4,21);

	for(int i=0;i<4;++i)
    {
        cout<<hex<<(int)buffer[i]<<" ";
    }

	return 0;
}

就是memset这种，5行代码足够了。

#49

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

//如果是对某个变量进行置位操作的话，也可以使用宏，只置上需要置位的位段，其他位保持不变
#define BIT_SET(val, low, hig) ((val) |= (((1 << ((hig) - (low) + 1)) - 1) << (low)))

//在数组上置位操作，只置上需要置位的位段，其他位保持不变
void bit_set(unsigned char *buffer, int low, int hig)
{
    int aux_low = (((low + 7) >> 3) << 3);
    int aux_hig = ((hig >> 3) << 3);
    int start, end;

    //低
    BIT_SET(buffer[low >> 3], (low % 8), aux_low % 8);

    //中
    for (start = aux_low >> 3, end = aux_hig >> 3; start < end; start++)
        buffer[start] = 0xff;

    //高
    BIT_SET(buffer[hig >> 3], (aux_hig % 8), hig % 8);
}

int main()
{
    int i;
    unsigned int ui = 0;
    unsigned char array[] = "1234567890";

    printf("%#.8x\n", BIT_SET(ui, 4, 21));
    
    bit_set(array, 2, 18);
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
        printf("%#.2x ", array[i]);

    system("pause");
    return 0;  
}

#50

引用 49 楼 we_sky2008 的回复:

C/C++ code

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

//如果是对某个变量进行置位操作的话，也可以使用宏，只置上需要置位的位段，其他位保持不变
#define BIT_SET(val, low, hig) ((val) |= (((1 << ((hig) - (low) + 1)) - 1) << (low)))

//在数组上置位操作……

当然，宏会有副作用，可以使用inline函数替换

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

//对某个变量进行置位操作的话，只置上需要置位的位段，其他位保持不变
inline unsigned int BIT_SET(unsigned int val, int low, int hig)
{
    return (((1 << ((hig) - (low) + 1)) - 1) << (low));
}

//在数组上置位操作，只置上需要置位的位段，其他位保持不变
void bit_set(unsigned char *buffer, int low, int hig)
{
    int aux_low = (((low + 7) >> 3) << 3);
    int aux_hig = ((hig >> 3) << 3);
    int start, end;

    //低
    buffer[low >> 3] |= BIT_SET(buffer[low >> 3], (low % 8), aux_low % 8);

    //中
    for (start = aux_low >> 3, end = aux_hig >> 3; start < end; start++)
        buffer[start] = 0xff;

    //高
    buffer[hig >> 3] |= BIT_SET(buffer[hig >> 3], (aux_hig % 8), hig % 8);
}


int main()
{
    int i;
    unsigned int ui = 0;
    unsigned char array[] = "1234567890";

    printf("%#.8x\n", BIT_SET(ui, 4, 21));
    
    bit_set(array, 9, 21);
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
        printf("%#.2x ", array[i]);

    system("pause");
    return 0;  
}