给定自然数 A，试求一自然数 B，以满足等式 A <= B = (1<<n) < 2A

wolfkin

给定一自然数 A，试求一自然数 B，以满足等式
A <= B = (1<<n) < 2A
n 亦为自然数。

请给出你认为最简单的方法及代码。

sewenew

#include <stdio.h>
int main()
{
        int A , tempA ;
        int n = 0 ;
        scanf( "%d" , &A ) ;
        tempA = A ;
        for( ; A ; A/=2 )
                n++ ;
        if( (1<<n) == 2*tempA )
                n-- ;
        printf( "B = %d\n" , 1<<n ) ;
        exit(0) ;
}

[ 本帖最后由 sewenew 于 2007-7-11 16:57 编辑 ]

sewenew

#!perl
use strict ;
my $A ;
chomp( $A = <STDIN> ) ;
my $tempA = $A ;
my $n ;
while( $A )
{
        $n++ ;
        $A/=2 ;
        $A =~ s/\..*// ;
}
$n-- if( (1<<$n) == 2 * $tempA ) ;
print 1<<$n ;

nkcsx

1. 
   
2. sub Fun {
   
3.         my $min = shift;
   
4.         my $max = $min << 1;
   
5.         my $res = 1;
   
6.         $res <<= 1 while ( ( $min >>= 1 ) != 1 );
   
7.         $res <<= 2;
   
8.         $res == $max ? $res >> 1 : $res;
   
9. }
   
10. 
    
11. print Fun($A);
    

复制代码

nkcsx

o,和楼上的一样了。：）

shhgs

1. 
   
2. sub func {
   
3.     my $n = shift;
   
4.     my $result = 1;
   
5.     $result <<= 1 until $result >= $n;
   
6.     return $result;
   
7. }
   

复制代码

[ 本帖最后由 shhgs 于 2007-7-12 19:49 编辑 ]

shhgs

如果是人思考的话，很简单，把数字转换成两进制的，看是不是2的n次方。是的话返回，不是的话，只保留第一个1,后面全部修改成 0,然后补一个零返回。

如果知道这个数的区间，找一个掩码与一下最快。不过现在不知道，所以直接移位了。

[ 本帖最后由 shhgs 于 2007-7-12 03:53 编辑 ]

nkcsx

原帖由 shhgs 于 2007-7-12 04:38 发表

sub func {
    my $n = shift;
    my $result = 1;
    while ( $result < $n) {
       $result = $result  

我怎么会想到把原数除2..直接这样乘就行了.

nkcsx

原帖由 shhgs 于 2007-7-12 04:47 发表
如果是人思考的话，很简单，把数字转换成两进制的，看是不是2的n次方。是的话返回，不是的话，只保留第一个1,后面全部修改成 0,然后补一个零返回。

如果知道这个数的区间，找一个掩码与一下最快。不过现在不 ...

甚是，改写一下

1. 
   
2. my $result = oct('0b1'.('0' x (length sprintf "%b", $num)));
   
3. 
   
4. print $result == $num << 1 ? $result >> 1 : $result;
   

复制代码

wolfkin

我这里给出一个解法。

我们知道，二进制数
    ((1<<n)-1)
的0、1是连续，不会出现0、1混合出现的情形。
将此数右移一位即为
    ((1<<(n-1))-1)
此两数相异或的结果就是(1<<(n-1))。

按题意，
    A <= B = (1<<n) < 2A
则
    A <= B = (1<<n) < 2A <= (1<<(n+1))
如果我们能够通过A构造出((1<<(n+1))-1)，就可以将其右移一位而得到((1<<n)-1)，再将这两个数想异或，就能得到(1<<n)了，即为所示之B。

按上式，(2A-1)肯定会小于(1<<(n+1))，但又会大于(1<<n)，
所以，我们先求
    B = (2A-1)
将B右移一位后再与B做或操作，则得到的B值就会更接近于((1<<(n+1))-1)。如果我们重复这样的步骤，就肯定能得到((1<<(n+1))-1)。
但要重复多少次呢？
假设最开初的B为(1<<n)，则一次之后为3B/2，再一次后为7B/4，再一次后为15B/8……
很明显，数据有多少位，就要重复多少次。
按前假设，
第一次后数据至少有两位1相邻的，可以将得到的B右移两位再或到B上，就可以得到4位相邻的1了……
如此，若总共有数N位，则最多需要重复(1+log2(N))次就行了。

这样也存在问题，我们给出的数是没有限制的，但这个算法却需要限制。还请哪位给完善一下。

下面给出一个检测程序，

#!/usr/bin/perl -w

for ($n=1; $n<(1<<16); $n++)
{
        printf "%016b %6d", $n, $n;
        $_ = 2 * $n - 1;
        printf "\t%016b %6d", $_, $_;
        $_ = $_ | ($_ >> 1);
        printf "\t%016b %6d", $_, $_;
        $_ = $_ | ($_ >> 2);
        printf "\t%016b %6d", $_, $_;
        $_ = $_ | ($_ >> 4);
        printf "\t%016b %6d", $_, $_;
        $_ = $_ | ($_ >> ;
        printf "\t%016b %6d", $_, $_;
        $_ = $_ ^ ($_ >> 1);
        printf "\t%016b %6d", $_, $_;
        $t=$_;
        while ($t)
        {
                $_ = 1 & $t;
                $t = $t >> 1;
                if ($_ && $t)
                {
                        print STDERR "!!!\t$n";
                        last;
                }
        }

        print "\n";
}

[ 本帖最后由 wolfkin 于 2007-7-13 12:07 编辑 ]