## Help with some C (binary operations)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

### Help with some C (binary operations)

So I've been given a series of tasks to complete in C. Problem is, we really haven't gone over very much, and the instructor has crippled me by disallowing several operations and options that I would normally use.

Down below is my current code so far, including all the specific instructions, but as it includes work I have completed, I'll summarize here:

Rules:
1. max constant we can use is 0xff
2. the only operations we can use are: ! ~ & ^ | + << >>
so no subtraction
also, sometimes some of the operations are banned for certain functions
3. Can't make or call any functions
4. Can't use any control constructs (if, do, while, for, switch, etc.) or non-specified operations (&&, ||, -, ?)
5. No casting of any kind

Assumptions:
1. My machine is 32-bit and uses 2s complements
2. Right shifts are arithmetic

Things I'm having special trouble with:

1. logicalShift
Spoiler:
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 1 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int
logicalShift(int x, int n) {
return (x << n);

Can't think of anything on this

2. bitCount
Spoiler:
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 1 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int
logicalShift(int x, int n) {
return (x << n);

The only thing I could think of here would be to keep shifting it to the right, adding the final bit each time, but sadly for loops are disallowed.

3. Bang
Spoiler:
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int
bang(int x) {
return 2;
}

Honestly I'm not entirely sure what the bang does. We haven't gone over it in class at all and google hasn't been very helpful. I do know that if you say something like !( x == y ) it would mean x is not equal to y, but logical operators are pretty much all kicked out (no == allowed).

4. leastBitPos
Spoiler:
/*
* leastBitPos - return a mask that marks the position of the
* least significant 1 bit. If x == 0, return 0
* Example: leastBitPos(96) = 0x20
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 4
*/
int
leastBitPos(int x) {
return x&(-x);
}

Now I actually found a solution here, but my teacher said it's invalid since I used a negative mark...

Spoiler:
/*
* addOK - Determine if can compute x+y without overflow
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int
int b = x >> 31;
int c = y >> 31;
int d = (b>>(0<<31))&0xffffffff;
int e = (c>>(0<<31))&0xffffffff;
int a = (d + e) >> 1;
return !(a == 1);

The problem with this is basically the right logical shift that I need to do, so once that goes tumbling down this one will be simple.

There are more at the bottom that I haven't got yet, but I haven't started on them yet. I'm going to continue working on them, but any help you could give would be greatly appreciated!

Code: Select all
`You will provide your solution to the Data Lab byediting the collection of functions in this source file.CODING RULES: Replace the "return" statement in each function with oneor more lines of C code that implements the function. Your code must conform to the following style: int Funct(arg1, arg2, ...) {  /* brief description of how your implementation works */  int var1 = Expr1;  ...  int varM = ExprM;      varJ = ExprJ;      ...      varN = ExprN;  return ExprR;}Each "Expr" is an expression using ONLY the following:1. Integer constants 0 through 255 (0xFF), inclusive. You are   not allowed to use big constants such as 0xffffffff.2. Function arguments and local variables (no global variables).3. Unary integer operations ! ~4. Binary integer operations & ^ | + << >>    Some of the problems restrict the set of allowed operators even further.Each "Expr" may consist of multiple operators. You are not restricted toone operator per line.You are expressly forbidden to:1. Use any control constructs such as if, do, while, for, switch, etc.2. Define or use any macros.3. Define any additional functions in this file.4. Call any functions.5. Use any other operations, such as &&, ||, -, or ?:6. Use any form of casting. You may assume that your machine:1. Uses 2s complement, 32-bit representations of integers.2. Performs right shifts arithmetically.3. Has unpredictable behavior when shifting an integer by more   than the word size.EXAMPLES OF ACCEPTABLE CODING STYLE:/* * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31 */int pow2plus1(int x) {  /* exploit ability of shifts to compute powers of 2 */  return (1 << x) + 1;}/* * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 */int pow2plus4(int x) {  /* exploit ability of shifts to compute powers of 2 */  int result = (1 << x);  result += 4;  return result;}NOTES:1. Use the dlc (data lab checker) compiler (described in the handout) to    check the legality of your solutions.2. Each function has a maximum number of operators (! ~ & ^ | + << >>)   that you are allowed to use for your implementation of the function.    The max operator count is checked by dlc. Note that '=' is not    counted; you may use as many of these as you want without penalty.3. Use the btest test harness to check your functions for correctness.4. The maximum number of ops for each function is given in the   header comment for each function. If there are any inconsistencies    between the maximum ops in the writeup and in this file, consider   this file the authoritative source.              }#endif/* * STEP 3: Modify the following functions according the coding rules. *  *   IMPORTANT. TO AVOID GRADING SURPRISES: *   1. Use the dlc compiler to check that your solutions conform *      to the coding rules. *   2. Use the btest test harness to check that your solutions produce  *      the correct answers. Watch out for corner cases around Tmin and Tmax. *//*  * bitNor - ~(x|y) using only ~ and &  *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8 *   Legal ops: ~ & *   Max ops: 8 *   Rating: 1 */intbitNor(int x, int y) {  return (~x)&(~y);}/*  * bitXor - x^y using only ~ and &  *   Example: bitXor(4, 5) = 1 *   Legal ops: ~ & *   Max ops: 14 *   Rating: 2 */intbitXor(int x, int y) {  int a = x&(~y);  int b = (~x)&y;  return ~((~a)&(~b));}/*  * isNotEqual - return 0 if x == y, and 1 otherwise  *   Examples: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1 *   Max ops: 6 *   Rating: 2 */intisNotEqual(int x, int y) {  return !(x == y); // Invalid}/*  * getByte - Extract byte n from word x *   Bytes numbered from 0 (LSB) to 3 (MSB) *   Examples: getByte(0x12345678,1) = 0x56 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 6 *   Rating: 2 */intgetByte(int x, int n) {  return (x>>(n<<3))&0xff;}/*  * copyLSB - set all bits of result to least significant bit of x *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 5 *   Rating: 2 */intcopyLSB(int x) {  return(x << 31) >> 31;}/*  * logicalShift - shift x to the right by n, using a logical shift *   Can assume that 1 <= n <= 31 *   Examples: logicalShift(0x87654321,4) = 0x08765432 *   Legal ops: ~ & ^ | + << >> *   Max ops: 16 *   Rating: 3  */intlogicalShift(int x, int n) {  return (x << n);}/* * bitCount - returns count of number of 1's in word *   Examples: bitCount(5) = 2, bitCount(7) = 3 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 40 *   Rating: 4 */intbitCount(int x) {  return 2;}/*  * bang - Compute !x without using ! *   Examples: bang(3) = 0, bang(0) = 1 *   Legal ops: ~ & ^ | + << >> *   Max ops: 12 *   Rating: 4  */intbang(int x) {  return 2;}/*  * leastBitPos - return a mask that marks the position of the *               least significant 1 bit. If x == 0, return 0 *   Example: leastBitPos(96) = 0x20 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 6 *   Rating: 4  */intleastBitPos(int x) {  return x&(-x);}/*  * TMax - return maximum two's complement integer  *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 4 *   Rating: 1 */inttmax(void) {  return 2147483647;}/*  * isNonNegative - return 1 if x >= 0, return 0 otherwise  *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1. *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 6 *   Rating: 3 */intisNonNegative(int x) {  return 2;}/*  * isGreater - if x > y  then return 1, else return 0  *   Example: isGreater(4,5) = 0, isGreater(5,4) = 1 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 24 *   Rating: 3 */intisGreater(int x, int y) {  return 2;}/*  * divpwr2 - Compute x/(2^n), for 0 <= n <= 30 *  Round toward zero *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 15 *   Rating: 2 */intdivpwr2(int x, int n) {  return 2;}/*  * absVal - absolute value of x (except returns TMin for TMin) *   Example: absVal(-1) = 1. *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 10 *   Rating: 4 */intabsVal(int x) {  return 2;}/*  * addOK - Determine if can compute x+y without overflow *   Example: addOK(0x80000000,0x80000000) = 0, *            addOK(0x80000000,0x70000000) = 1,  *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 20 *   Rating: 3 */intaddOK(int x, int y) {  int b = x >> 31;  int c = y >> 31;  int d = (b>>(0<<31))&0xffffffff;  int e = (c>>(0<<31))&0xffffffff;  int a = (d + e) >> 1;  return !(a == 1); // WHY THIS NO WORK!?}`
Slippery John

Posts: 4
Joined: Wed Mar 14, 2012 6:28 pm UTC

### Re: Help with some C (binary operations)

There was a thread a while back from, I presume, someone else taking the same class... some decent hints in there, for bitCount and logicalNot, in particular.

Some small hints for the others:
(1) Consider (a >> 1) and logicalShift(a, 1)... think about what they mean. Can you turn the former into the latter, somehow?
(4) You're on the right track here. Can you implement the unary minus given the operations you have available? How does 2's complement work?
(5) It looks like all you're doing is checking if the first bit is set on both numbers? That isn't going to be enough - remember that there are carries, too. In the extreme case, 0x7FFFFFFF + 1 is going to overflow. Also, remember your numbers are 2's complement. A hint: if you add two positive numbers, and they don't overflow, what can the range of the result be? If they do overflow, what can the range of the result be?
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6958
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Help with some C (binary operations)

the solution is that your instructor should be fired and replaced by somebody who wants to teach you how to program in C

edit - I am assuming that this is a course on C, not some course on artificially convoluted logic problems
And so I moved that very day into the heart of a quince, where the seeds are few and almost silent.

zmic

Posts: 274
Joined: Fri Mar 02, 2012 10:38 pm UTC

### Re: Help with some C (binary operations)

zmic wrote:the solution is that your instructor should be fired and replaced by somebody who wants to teach you how to program in C

edit - I am assuming that this is a course on C, not some course on artificially convoluted logic problems

It's also perfectly acceptable if the course is supposed to involve learning about number representations and such.

I'd go so far as to say these are actually pretty decent questions for any low-levelish CS class, with maybe the exception of the restriction that you can't write your own functions. Just as long as the class doesn't make a habit of it.
EvanED

Posts: 3929
Joined: Mon Aug 07, 2006 6:28 am UTC

### Re: Help with some C (binary operations)

zmic wrote:the solution is that your instructor should be fired and replaced by somebody who wants to teach you how to program in C

edit - I am assuming that this is a course on C, not some course on artificially convoluted logic problems

Well the class is Introduction to Computer Systems, so C is more of a means to an end rather than the objective.

as for the other things:
I'll make a point to check out that thread

1) I think I have vague ideas about how to do logicalShift, I'll see if anything comes up as I sleep
4) We are specifically forbidden from using - in any form
5) I think I'm going to have to go over 2s complements some more. We didn't cover them very well in class, and it seems like they're going to be integral to solving these

Thanks for the help and especially the quick responses!
Slippery John

Posts: 4
Joined: Wed Mar 14, 2012 6:28 pm UTC

### Re: Help with some C (binary operations)

Slippery John wrote:4) We are specifically forbidden from using - in any form

I know, what I mean is... can you figure out how to build something that works in the same way as -, with only the operations you have available?

In two's complement, how does negation actually work?
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6958
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Help with some C (binary operations)

phlip wrote:
Slippery John wrote:4) We are specifically forbidden from using - in any form

I know, what I mean is... can you figure out how to build something that works in the same way as -, with only the operations you have available?

In two's complement, how does negation actually work?

Got it!

For those who are interested, this is what I ended up with:
Spoiler:
int
leastBitPos(int x) {
return x&(~x + 1);
}

(that's a tilde in there)

EDIT: I also just figured out logicalShift! Since C will perform a logical shift if there's a zero there, I had better make sure that's all there is, I can then use that to make a mask to get rid of all those pesky leading 1s
Spoiler:
int
logicalShift(int x, int n) {
}

Once again, those are tilde's
Slippery John

Posts: 4
Joined: Wed Mar 14, 2012 6:28 pm UTC

### Re: Help with some C (binary operations)

Looks good to me... however this term could be simplified slightly:
Slippery John wrote:(~1+1)
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6958
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Help with some C (binary operations)

zmic wrote:the solution is that your instructor should be fired and replaced by somebody who wants to teach you how to program in C

edit - I am assuming that this is a course on C, not some course on artificially convoluted logic problems
Most programs don't have classes in specific languages. I don't think I was instructed on any language directly, other than Java in my intro course, the rest treated the language (C, C++, Python, ML, SPARC, MIPS) as a tool you had to learn on your own time. I learned C in the same sort of class, though the more sadistic assignments were in assembly (and hand-translated into machine code, which seemed pointless at the time but was a great help when I had to design my own in a later class).

TheAmazingRando

Posts: 2304
Joined: Thu Jan 03, 2008 9:58 am UTC
Location: San Diego, CA

### Re: Help with some C (binary operations)

TheAmazingRando wrote:
zmic wrote:the solution is that your instructor should be fired and replaced by somebody who wants to teach you how to program in C

edit - I am assuming that this is a course on C, not some course on artificially convoluted logic problems
Most programs don't have classes in specific languages. I don't think I was instructed on any language directly, other than Java in my intro course, the rest treated the language (C, C++, Python, ML, SPARC, MIPS) as a tool you had to learn on your own time. I learned C in the same sort of class, though the more sadistic assignments were in assembly (and hand-translated into machine code, which seemed pointless at the time but was a great help when I had to design my own in a later class).

For what it's worth, the MIT OpenCourseWare has like, three classes about specific languages, and even those are the special four-week exploratory classes that the university runs in January.

The rest, even the basic introductory courses, all have basically everything phrased as "a variable is essentially a name we've bound to a value. In Scheme, we declare a variable by using (define <variable> <value>). Variables have many uses, such as..."

So, yeah. Not so much in terms of language instruction, generally, only inasmuch as the language is a typical example of some concept that's being discussed.

Shivahn

Posts: 2173
Joined: Tue Jan 06, 2009 6:17 am UTC

### Re: Help with some C (binary operations)

phlip wrote:Looks good to me... however this term could be simplified slightly:
Slippery John wrote:(~1+1)

Oh how silly of me, should be ~0

Alright, now of the originals I asked about the only one left is bitCount

I am also now struggling with these:

isGreater (checks to see if x is greater than y)
Spoiler:
Code: Select all
`/*  * isGreater - if x > y  then return 1, else return 0  *   Example: isGreater(4,5) = 0, isGreater(5,4) = 1 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 24 *   Rating: 3 */intisGreater(int x, int y) {  return (x + (~y + 1)) >> 31 & 1;}`

absVal (computes the absolute value of x)
Spoiler:
Code: Select all
`/*  * absVal - absolute value of x (except returns TMin for TMin) *   Example: absVal(-1) = 1. *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 10 *   Rating: 4 */intabsVal(int x) {  int shift1 = x << 1;  int mask = ~(1<<31)>>(1+(~1+1));  return (shift1 >> 1) & mask;`

I'm also re-doing my isNotEqual since I used illegal operators, but I feel like I'm close to a breakthrough on that.

EDIT: I can think of a way to do the bitCount, but it would use way too many operators
EDIT2: I got the isGreater
EDIT3: got the isNotEqual
EDIT4: I got something for bitCount and its within the max ops, but I can't help but think there's a better way:
Spoiler:
Code: Select all
`/* * bitCount - returns count of number of 1's in word *   Examples: bitCount(5) = 2, bitCount(7) = 3 *   Legal ops: ! ~ & ^ | + << >> *   Max ops: 40 *   Rating: 4 */intbitCount(int x) {  int maskBase1 = 0x55;  int mask1 = (maskBase1 << 8) | maskBase1;  mask1 = (mask1 << 8) | maskBase1;  mask1 = (mask1 << 8) | maskBase1;  int maskBase2 = 0x33;  int mask2 = (maskBase2 << 8) | maskBase2;  mask2 = (mask2 << 8) | maskBase2;  mask2 = (mask2 << 8) | maskBase2;  int maskBase3 = 0xf;  int mask3 = (maskBase3 << 8) | maskBase3;  mask3 = (mask3 << 8) | maskBase3;  mask3 = (mask3 << 8) | maskBase3;    int mask4 = (0xff << 16) | 0xff;  int mask5 = (0xff << 8) | 0xff;  int count = (x & mask1) + ((x >> 1) & mask1);  count = ((count >> 2) & mask2) + (count & mask2);  count = ((count >> 4) + count) & mask3;  count = ((count >> 8) + count) & mask4;  count = ((count >> 16) + count) & mask5;    return count;}`

I basically just used shifts and or's to create all the masks I needed. The thing is, those max ops were set to catch horrendously inefficient solutions, so I really don't want it to be that long (there are 39 ops in my solution).
Slippery John

Posts: 4
Joined: Wed Mar 14, 2012 6:28 pm UTC

### Re: Help with some C (binary operations)

Use as few hints as you can. I'd advise waiting at least 5 minutes between reading each hint to get a decent chance to figure out what the hint means.

Hint 1:
Spoiler:
Use xor.

Hint 2:
Spoiler:

Hint 3:
Spoiler:
Construct the masks in the opposite order.

Hint 4:
Spoiler:

Hint 5:
Spoiler:
Create a function that returns (in binary) 0101 when passed in 0011, and you aren't allowed to use constants on the left hand side of any operation.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10209
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove