ÓйØλ²Ù×÷¼¼ÇÉÃæÊÔÌâ
1£¬Í³¼ÆÒ»¸öÕûÊý¶þ½øÖÆʽ¡®1¡¯µÄ¸öÊý£º
¼ÙÈçÒ»¸öÊýn=0¡Á1110 0010£¬ÄÇôn ¨C 1 = 0¡Á1110 0001, Ò²¾ÍÊÇ°Ñ×îÓұߵÄÄǸö1±äΪ0£¬È»ºó×ó±ßµÄ¶¼±ä³É1
Èç¹ûÈÃËûÃÇ¡°Ó롱ÔËËãµÄ»°£¬¾ÍµÈÓÚ°ÑÊýnµÄ×îÓұߵÄ1±äΪ0£¬ÆäÓàµÄλ²»±ä¡£ÕâÑùÑ»·m´Î(mλ1µÄ¸öÊý£©¾Í¿ÉÒÔ°Ñn±ä³É0£¬´ËʱҲ¾Í¿ÉÒÔͳ¼Æ³ö1µÄ¸öÊýÁË¡£
int NumOnes(int number)
{
int cnt = 0;
while(number != 0)
{
number &= (number ¨C 1);
cnt++;
}
return cnt;
}
2.¡¢¸ø¶¨Ò»¸ö32bitµÄÊýÖµ£¬Èç¹ûÊä³ö±ÈÌØλ·´×ªºóµÄÖµ£¬Èç¶ÔÓÚ4bitµÄ¶þ½øÖÆÖµ1011£¬·×ªºóΪ1101¡£ÒªÇó¸´ÔÓ¶ÈO(lgn),n Ϊ±ÈÌØλÊý
ÕâµÀÌâÖ÷ÒªÊÇÓÐʱ¼ä¸´ÔӶȵÄÏÞÖÆ£¬¼´lgn´Î£¬Ò²¾ÍÊÇ˵32bitÄãÖ»ÄÜÔËËã5´Î¾ÍÒªµÃ³ö½á¹û³öÀ´¡£
int GetInverse(int source)
{
int target = 0;
while (source > 0)
{
target = (target << 1) | (source & 0¡Á01);
source = source >> 1;
}
return target;
}
Õâ¸öË㷨ʱ¼ä¸´ÔÓ¶ÈλO£¨n£©.²»·ûºÏÌâÄ¿ÒªÇó¡£
ÆäʵÎÒÃÇ¿ÉÒÔÏëÏ룬ÓÐ32bit£¬¿Ï¶¨ÒªÔËÓ÷ÖÖεķ½·¨
µÚ1´Î£ºÎÒÃÇ¿ÉÒÔÏȶԵÚ0£¬1룬ÈÃËûÃÇ»¥»»£¬£¨2£¬3£©£¬ £¨4£¬5£©£¬¡£¡£¡££¬£¨30£¬31£©ÕâЩ¶Ôµ÷λÖÃÈ磺
0¡Á1001 0001 ==> 0x 0110 0010
µÚ2´Î£º¿ÉÒÔ¶Ô£¨0£¬1£¬2£¬3£©£¬£¨4£¬5£¬6£¬7£©£¬¡£¡£¡££¬£¨28£¬29£¬30£¬31£©£¬È磺
0x 0110 0010 ==> 0x 10011000
µÚ3´Î£º¶Ô£¨0,1,2,3,4,5,6,7)¡£¡£¡££¬ÈÃËûÃǶԵ÷λÖÃ
µÚ4´Î£¨0£¬1£¬2£¬¡£¡£¡££¬15£©
µÚ5´Î£¨0£¬¡£¡£¡££¬31£©½áÊø.
ÏÖÔÚÒª½â¾öÔõÑù´¦ÀíÈõÚiλºÍµÚi+1λ¶Ôµ÷£¬Ïñ£¨0£¬1£©
¿ÉÒÔÕâÑùÍê³É; y = 0¡Á55555555 ¶þ½øÖÆλ£º0¡Á0101 0101 0101 0101 0101 0101 0101 0101
x = (((x >> 1) & y) | ((x & y) << 1));
ÏÖ ÔÚÀ´½âÊÍÒ»ÏÂÕâ¸ö²Ù×÷£º((x>>1)&y) Æäʵ¾ÍÊÇÏÈ°ÑxÓÒÒÆһ룬ÔÚºÍy×ö¡°Ó롱ÔËË㣬µÃ³öµÄ½á¹û¾ÍÊÇÈ¡³öÁËxÓÒÒÆһλºóËùÓеĵÚ0,2,4,6,8,¡., 30λµÄÊý£¬ÒòΪÕâÀïyÔÚÕâλÉÏÊÇ1ÆäËûλΪ0£¬Ò²¾ÍÊÇÔÀ´xµÄµÚ1£¬3£¬5£¬7£¬¡£¡£¡£31λÊý¡£
¶ø£º(x & y) << 1 ÊÇÈ¡³öxµÄµÚ1£¬3£¬5£¬7£¬¡£¡£¡££¬31λ£¬È»ºó°ÑËü×óÒÆ£¬
×îºóÔÚ°ÑËûÃÇ¡°»ò¡±ÔËË㣬ÕâÑù¾Í´ïµ½ÁË£¨0£¬1£©£¬£¨2£¬3£©£¬¡£¡£¡££¬Î»¶Ôµ÷µÄЧ¹ûÁË¡£
ºóÃæµÄÇé¿öÀàËÆ£¬ËùÒÔ×îÖÕ´úÂëÊÇÕâÑùµÄ£º
unsigned int reverse_32bit( unsigned int x)
{
unsigned int y = 0¡Á55555555;
x = (((x >> 1) & y) | ((x & y) << 1));
y = 0¡Á33333333;
x = (((x >> 2) & y) | ((x & y) << 2));
y = 0x0f0f0f0f;
x = (((x >> 4) & y) | ((x LOR: #000000¡å>& y) << 4));
y = 0x00ff00ff;
x = (((x >> 8) & y) | ((x & y) << 8));
return((x >> 16) | (x << 16));
}