2

数値が与えられた場合、2 進表現で同じ数の 1 ビットを持つ、次に高い数値と前の数値を見つける必要があります。

私の解決策はブルートフォースアプローチです。つまり、同じ数の1がある場合は、数を増やして1の数を数え、それを印刷します

前の番号については、上記と同じアプローチ

すべての数字をチェックする代わりに、最適化された解決策はありますか?

4

2 に答える 2

6

次に大きい数字を取得するには、 の最初のインスタンスを01右から検索し、これを に変更し10ます。次に1、スワップされたビットの右側にあるすべての s を最下位の位置に折りたたみます。

例：

 ||
00110000 // 0x30 in hex

スワップ後:

 ||
01010000 // 0x50 in hex

次に、スワップされたビットの右側にあるすべての 1 を最下位の位置にまとめます。

 ||---->
01000001 // 0x41 in hex

前の番号を取得するには、右から始まる の最初のインスタンスを検索し、10それを に置き換え01ます。次に0、スワップされたビットの後のすべての s を最下位の位置に折りたたみます (または、1スワップされたビットの後のすべての s を最上位の位置に折りたたみます)。

例：

    ||
01001001 // 0x48 in hex

スワップ後:

    ||
01000101 // 0x45 in hex

次に、スワップされたビットの右側にあるすべての 0 を最下位の位置にまとめます。

    ||->
01000110 // 0x46 in hex

次に大きい数字と小さい数字の両方を表示する短いプログラムを次に示します。

#include <iostream>
#include <bitset>
#include <stdlib.h>

using namespace std;
#define NUMSIZE 8       // The number of bits to display

// Finds the first and second values, swaps them, and collapses.
void swap_and_collapse(bitset<NUMSIZE>& num, bool v1, bool v2, bool c) {
  // Find the v1 immediately followed by v2 in the number.
  int insert_pos = 0;
  for (int i=1; i<NUMSIZE; i++) {
    if ((num.test(i-1) == v2) && (num.test(i) == v1)) {
      // Found them.  Swap the values.
      num.flip(i-1); num.flip(i);
      break;
    } else {
      // Move any c bits to the beginning.
      if (num.test(i-1) == c) {
        num.flip(i-1);
        num.flip(insert_pos++);
      } // if (num.test(i-1) == c) 
    } // if ((num.test(i-1) == v2) && (num.test(i) == v1)) 
  } // for (int i=0; i<16; i++)
} // swap_and_collapse

int main(int argc, char* argv[]) {
  // Get the number from the command line and display in binary.
  int value = atoi(argv[1]);
  bitset<NUMSIZE> orig  (value);
  cout << "Original Number " << orig.to_ulong() << " is " << orig << endl;

  // Find the next higher number.
  bitset<NUMSIZE> higher(value);
  swap_and_collapse(higher, 0, 1, 1);
  // Find the next lower number.
  bitset<NUMSIZE> lower (value);
  swap_and_collapse(lower,  1, 0, 0);

  cout << "Higher number   " << higher.to_ulong() << " is " << higher << endl;
  cout << "Lower number    " <<  lower.to_ulong() << " is " <<  lower << endl;
} // main
于 2013-06-11T15:11:46.650 に答える
0

これは、1の数が等しい次の最大数を見つけるためのコードです

#include<iostream>
using namespace std;
int main()
{
int c;
cin>>c;
int n=c;
int c1=0;
while(((c&1)==0) && (c!=0) )
{
    c1++;
    c=c>>1;
}
cout<<"the no of zereos"<<c1<<endl;
cout<<c<<endl;
int c2=0;
while((c&1)==1)
{
    c2++;
    c=c>>1;
}
cout<<"no of ones"<<c2<<endl;
cout<<c;
int p=c1+c2;
n=n|(1<<p);
int a=1<<p;
int b=a-1;
cout<<endl<<b;
int mask=~b;
n=n&mask;
a=1<<(c2-1);
b=a-1;
n=n|b;
cout<<"\n"<<a;
cout<<"\n"<<n;

  }
于 2013-06-11T19:20:40.127 に答える