[bla!!]

Hey, I'm doing a homework problems and am very stuck.

This is your basic bitwise operator problem.

I have this one working for small values, but when they approach the maximum 2's compliment size, they return the wrong value.

/*
 * fitsBits - return 1 if x can be represented as an
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n)
{


  int shift = 1 << n;
  int test = (shift ^ (x << 1)) >> n;

  return !!test;


}

If anyone's a guru at these problems, could you give me a hand. Thare are other's that I'm working on also, but I am very lost.

[gab00n]

This is how i did it:

#include <iostream>

using namespace std;
int fitsBits(int x, int N);
int main()
{
	int num;
	int bits;
	
	cout<<"Enter the number and bit length: ";
	cin>>num>>bits;
	cout<<endl;
	cout<<fitsBits(num, bits);
	
	return 0;
}

int fitsBits(int x, int N) 
{ 
 int fits = - (x & (1 << N - 1)); 
 for(int i = N - 2; i >= 0; --i) 
 {
 	fits |= (x & (1 << i));
 }
 
 if(fits == x)
 {
 	return 1;
 }
 else
 {
 	return 0;
 }
}

[bla!!]

Awesome. I can't acutally use looping or conditional structures, but this gives me a better idea of how to go about it.

Thanks!

[bla!!]

I finally got it, if you're curious at all.

int fitsBits(int x, int n)
{
   mask = x >> 31;
   size = n + ~0x0;

   tmp1 = ~x & mask;
   tmp2 = x & ~mask;

   return !((tmp1 + tmp2) >> size);

}

Supposedly you can do it in only 6 operations, but I'm still baffled by that. This one takes 10 operations.

[gab00n]

Yeah it looks good man, maybe i'll try and see if i can get it working in six operations.

[bla!!]

Finally got the version in 6 operations.

It seems so obvious once you figure it out. Stupid computers!

int fitsBits(int x, int n)
{
  int shift = 33 + ~n;
  int x2 = x << shift;
  int x3 = x2 >> shift;

  return !(x3 ^ x);
}

[gab00n]

Excellent man, i tested it and it works great.