Member Avatar for chrjs

I am doing this assignment for my computer science course, and I have to write a function that determines if 'x' can fit into an n-bit, two's complement integer.

I am not allowed to use any control statements or operators other than the ! ~ & ^ | + << >> operators. I am also not allowed to use any macros or function calls. I am also not allowed to use any form of casting or any variables that are not of type int, including arrays, structs and unions.

This is assuming a 32-bit, two's complement integers.

This is the code I have written so far. I doesn't really work well, and I can't find what I am doing wrong, any help would be appreciated.

/*
This function is supposed to check if an integer with the 
value of 'x' would fit inside an integer with a 'n' bits

Returns non-zero is 'x' fits in a integer with 'n' bits
Returns zero if it doesn't
*/
int fitsBits(int x, int n)
{
	//declare variables
	int sv, tx;

	//this calculates the 32 - (n + 1)
	//this is the value to shift 'x' to calculate 'tx'
	sv = 32 + (~n);
	
	//shift 'x' left sv bits and assigns it to 'tx', 
	//this is later shifted back the same amount
	//this is done so that 'tx' will equal
	//a version of 'x' that is truncated to fit in 'n' bits
	tx = x << sv;
	
	//make sure leftmost bit is zero
	//(to make sure right shift is equivalent to logical shit)
	tx = tx & ~(0x01 << 31);

	//shift 'tx' back
	tx = tx >> sv;

	//calculate bitwise xor of tx and x
	//this checks if there are any bits are outside of the range designated by 'n'	
	return tx ^ x;
}
Edited by chrjs because: n/a
  • 3 Contributors
  • 3 Replies
  • 3K Views
  • 3 Years Discussion Span
  • Latest Post Latest Post by mbelenske

Dani AI

Generated

The key is to rely on arithmetic sign extension, not a logical shift. As hinted, clearing the top bit before shifting right forces a logical shift and breaks negatives. In two’s complement, an arithmetic right shift replicates the sign bit; that is exactly what you want when checking whether the high 32-n bits are all copies of the sign. (en.wikipedia.org)

A concise way to do this without any control flow (and using only the allowed operators) is to avoid the truncate-then-restore pattern entirely. If x fits in an n-bit two’s-complement integer, then x >> (n-1) must be either 0 (nonnegative case) or all 1s (negative case). That yields a simple check:

int fitsBits(int x, int n) {
    int s = x >> (n + ~0);      /* shift by n-1 using only + and ~ */
    return !s | !(s ^ ~0);      /* 1 if s == 0 or s == -1 */
}

This handles negatives correctly because it depends on sign-propagating right shift. Note: in standard C, right-shifting a negative value is implementation-defined, but on mainstream two’s-complement targets it is an arithmetic shift, which aligns with the assignment’s stated assumptions. (en.wikipedia.org)

Two practical tips while testing: (1) confirm boundary cases for each n, e.g., the largest positive that should fit (2^(n-1)-1) and the most negative that should fit (-2^(n-1)); (2) ensure n is in [1,32], because any shift count >= the word width is undefined by the C standard (shifting by 32 on a 32-bit int, for example). Those checks prevent head-scratchers that are not algorithm bugs. (en.wikipedia.org)

Recommended Answers

All 3 Replies

Member Avatar for chrjs

Well, I found that I needed to change line 32 to return !(tx ^ x); , but the program doesn't work for negative numbers. It would be appreciated if anyone could give me an idea on how to account for the sign in this problem.

Edited by chrjs because: n/a
Member Avatar for nezachem

Take a close look at line 25. Are you sure you want a shift to be logical?

Member Avatar for mbelenske

My working Code. I believe if you remove line 25 it should work.

int fitsBits(int x, int n) 
{
        int a = (33 + (~n));
        int b = (x << a);
        int c = (b >> a);
        int e = !(c ^ x);
        return  e;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.