Member Avatar for jralexander137

I am having trouble understanding how to implement these problems in C using bit operators. I understand the basic logic gates and when I work them out on paper they work just not code wise. Any insight/help would be great.

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y) {
  return ~((~((~y)&x))&(~((~x)&y)));
}

/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y) {
  return ~((~x)|(~y));
}

/* 
 * isEqual - return 1 if x == y, and 0 otherwise 
 *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int isEqual(int x, int y) {
  return !(x ^ y);
}

This is the only one I can get working but I don't think I implemented correctly.

/*
 * isZero - returns 1 if x == 0, and 0 otherwise 
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x) {

//FINISHED.

  return !(x!=0);

}

And I can't use loops or conditionals.

Thanks Again.

  • 3 Contributors
  • 10 Replies
  • 874 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by jralexander137
Member Avatar for invisal

You don't understand the code or the code does not work properly? It seem to work properly for me.

Member Avatar for jralexander137

Maybe its the test code that I have to use to test it is not working right?

I mean for what I have is the logic correct? I'd post the test code that was given but it's like 330+lines long.

Member Avatar for invisal

If I am not wrong, it is logically correct.

Member Avatar for Dave Sinkula

Maybe its the test code that I have to use to test it is not working right?

I mean for what I have is the logic correct? I'd post the test code that was given but it's like 330+lines long.

Some quickie test code for my "playing along at home":

#include <stdio.h>

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y)
{
   return ~((~((~y)&x))&(~((~x)&y)));
}

/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y)
{
   return ~((~x)|(~y));
}

/* 
 * isEqual - return 1 if x == y, and 0 otherwise 
 *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int isEqual(int x, int y)
{
   return !(x ^ y);
}

/*
 * isZero - returns 1 if x == 0, and 0 otherwise 
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x)
{
   return !(x!=0);
}

int test_unary(const char *name, int (*f)(int), int value)
{
   int result = f(value);
   printf("%s(%d) = %d\n", name, value, result);
   return result;
}

int test_binary(const char *name, int (*f)(int, int), int x, int y)
{
   int result = f(x, y);
   printf("%s(%d,%d) = %d\n", name, x, y, result);
   return result;
}

#define printpair(x) #x,x

int main()
{
   test_binary(printpair(bitXor),  4, 5);
   test_binary(printpair(bitAnd),  6, 5);
   test_binary(printpair(isEqual), 5, 5);
   test_binary(printpair(isEqual), 4, 5);
   test_unary(printpair(isZero), 0);
   test_unary(printpair(isZero), 5);
   return 0;
}

/* my output
bitXor(4,5) = 1
bitAnd(6,5) = 4
isEqual(5,5) = 1
isEqual(4,5) = 0
isZero(0) = 1
isZero(5) = 0
*/
Member Avatar for jralexander137

I keep getting errors along these lines when I test bitAnd though these are the same general error type for the rest just a dif number for the should be parts.

Gives 2[0x]. Should be 0[0x0].

Then next line down.

Gives 2[0x2]. Should be -21474836[0x80000000].

Member Avatar for Dave Sinkula

For what inputs?

int main()
{
   test_binary(printpair(bitAnd),  0xC0000000, 0x80000000);
   return 0;
}

/* my output
bitAnd(-1073741824,-2147483648) = -2147483648
*/
Member Avatar for jralexander137

Here is the code that will test my methods. This is given and should not be modified.

I have tried to attach it.

/* 
 * CS:APP Data Lab 
 * 
 * btest.c - A test harness that checks a student's solution 
 *           in bits.c for correctness. 
 *
 * Copyright (c) 2001, R. Bryant and D. O'Hallaron, All rights reserved.
 * May not be used, modified, or copied without permission.
 *
 * Usage:
 *    -e <N>       Limit number of errors to report for single function to N
 *    -f <Name>    Check only the named function
 *    -g           Print compact grading summary (implies -v 0 and -e 0)
 *    -h           Print help message
 *    -a           Don't check team structure
 *    -r <N>       Give uniform weight of N for all problems
 *    -v <N>       Set verbosity level to N
 *                 N=0:  Only give final scores
 *                 N=1:  Also report individual correctness scores (default)
 * 
 * Each problem has a weight 1 to 4, which is defined in legallist.c.

 */
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "btest.h"

/* Globals defined in other modules */
extern team_struct team;    /* defined in bits.c */
extern test_rec test_set[]; /* defined in decl.c */
                            /* and generated from templates in ./puzzles */

/* Generate test values near "corner cases" */
#define TEST_RANGE 5
#define TEST_COUNT 33

/* Print only compact grading summary if set (-g) */
static int grade = 0;

/* Max errors reported per function (-e) */
static int error_limit = 1000;

/* If non-NULL, test only one function (-f) */
static char* test_fname = NULL;  

/* Should I used fixed weight for rating, and if so, what should it be? (-r)*/
static int global_rating = 0;

/* Return random value between min and max */
static int random_val(int min, int max)
{
    double weight = rand()/(double) RAND_MAX;
    int result = min * (1-weight) + max * weight;
    return result;
}

/* Generate the integer values we'll use to test a function */
static int gen_vals(int test_vals[], int min, int max)
{
    int i;
    int test_count = 0;

    /* If range small enough, then do exhaustively */
    if (max-32 <= min) {
	for (i = min; i <= max; i++)
	    test_vals[test_count++] = i;
	return test_count;
    }
    /* Otherwise, need to sample.
       Do so near the boundaries and for a few random cases */
    for (i = 0; i < TEST_RANGE; i++) {
	test_vals[test_count++] = min+i;
	test_vals[test_count++] = max-i;
	test_vals[test_count++] = (max+min-TEST_RANGE)/2+i;
	test_vals[test_count++] = random_val(min, max);
    }
    return test_count;
}

/* Test a function with zero arguments */
static int test_0_arg(funct_t f, funct_t ft, char *name, int report)
{
    int r = f();
    int rt = ft();
    int error =  (r != rt);

    if (error && report)
	printf("Test %s() failed.\n  Gives %d[0x%x].  Should be %d[0x%x]\n",
	       name, r, r, rt, rt);
    return error;
}

/* Test a function with one argument */
static int test_1_arg(funct_t f, funct_t ft, int arg1, char *name, int report)
{
    funct1_t f1 = (funct1_t) f;
    funct1_t f1t = (funct1_t) ft;
    int r, rt, error;

    r = f1(arg1);
    rt = f1t(arg1);
    error = (r != rt);
    if (error && report)
	printf("Test %s(%d[0x%x]) failed.\n  Gives %d[0x%x].  Should be %d[0x%x]\n",
	       name, arg1, arg1, r, r, rt, rt);
    return error;
}

/* Test a function with two arguments */
static int test_2_arg(funct_t f, funct_t ft, 
		      int arg1, int arg2, 
		      char *name, int report)
{
    funct2_t f2 = (funct2_t) f;
    funct2_t f2t = (funct2_t) ft;
    int r = f2(arg1, arg2);
    int rt = f2t(arg1, arg2);
    int error = (r != rt);

    if (error && report)
	printf(
	       "Test %s(%d[0x%x],%d[0x%x]) failed.\n  Gives %d[0x%x].  Should be %d[0x%x]\n",
	       name, arg1, arg1, arg2, arg2, r, r, rt, rt);
    return error;
}

/* Test a function with three arguments */
static int test_3_arg(funct_t f, funct_t ft,
	   int arg1, int arg2, int arg3,
	   char *name, int report)
{
    funct3_t f3 = (funct3_t) f;
    funct3_t f3t = (funct3_t) ft;
    int r = f3(arg1, arg2, arg3);
    int rt = f3t(arg1, arg2, arg3);
    int error = (r != rt);

    if (error && report)
	printf(
	       "Test %s(%d[0x%x],%d[0x%x],%d[0x%x]) failed.\n  Gives %d[0x%x].  Should be %d[0x%x]\n",
	       name, arg1, arg1, arg2, arg2, arg3, arg3, r, r, rt, rt);
    return error;
}

/* Test a function.  Return number of errors */
static int test_function(test_ptr t, int report) {
    int test_vals[3][TEST_COUNT];
    int test_counts[3];
    int errors = 0;
    int i;
    int a1, a2, a3;
    int args = t->args;

    /* Create test set */
    for (i = 0; i < 3; i++)
	test_counts[i] =
	    gen_vals(test_vals[i], t->arg_ranges[i][0], t->arg_ranges[i][1]);
    if (args == 0) {
	errors += test_0_arg(t->solution_funct, t->test_funct,
			     t->name, report && errors < error_limit);
    } else for (a1 = 0; a1 < test_counts[0]; a1++) {
	if (args == 1) {
	    errors += test_1_arg(t->solution_funct, t->test_funct,
				 test_vals[0][a1],
				 t->name, report && errors < error_limit);
	} else for (a2 = 0; a2 < test_counts[1]; a2++) {
	    if (args == 2) {
		errors += test_2_arg(t->solution_funct, t->test_funct,
				     test_vals[0][a1], test_vals[1][a2],
				     t->name, report && errors < error_limit);
	    } else for (a3 = 0; a3 < test_counts[2]; a3++) {
		errors += test_3_arg(t->solution_funct, t->test_funct,
				     test_vals[0][a1], test_vals[1][a2],
				     test_vals[2][a3],
				     t->name, report && errors < error_limit);
	    }
	}
    }

    if (!grade) {
	if (report && errors > error_limit)
	    printf("... %d total errors for function %s\n",
		   errors, t->name);
    }

    return errors;
}

/* Run series of tests.  Return number of errors */ 
static int run_tests(int report) {
    int i;
    int errors = 0;
    double points = 0.0;
    double max_points = 0.0;

    if (grade)
	printf("Score\tErrors\tFunction\n");

    for (i = 0; test_set[i].solution_funct; i++) {
	int terrors;
	double tscore;
	double tpoints;
	if (!test_fname || strcmp(test_set[i].name,test_fname) == 0) {
	    int rating = global_rating ? global_rating : test_set[i].rating;
	    terrors = test_function(&test_set[i], report);
	    errors += terrors;
	    if (test_set[i].args == 0)
		tscore = terrors == 0 ? 1.0 : 0.0;
	    else
		tscore = terrors == 0 ? 1.0 : terrors == 1 ? 0.5 : 0.0;
	    tpoints = rating * tscore;
	    points += tpoints;
	    max_points += rating;
	    if (grade)
		printf(" %.1f\t%d\t%s\n", tpoints, terrors, test_set[i].name);
	    if (report)
		printf("Test %s score: %.2f/%.2f\n",
		       test_set[i].name, tpoints, (double) rating);
	}
    }

    if (grade) 
	printf("Total points: %.2f/%.2f\n", points, max_points);
    else
	printf("Overall correctness score: %.2f/%.2f\n", points, max_points);

    return errors;
}

static void usage(char *cmd) {
    printf("Usage: %s [-v 0|1] [-hag] [-f <func name>] [-e <max errors>]\n", cmd);
    printf("  -e <n>    Limit number of errors to report for single function to n\n");
    printf("  -f <name> Check only the named function\n");
    printf("  -g        Print compact grading summary (implies -v 0 and -e 0)\n");
    printf("  -h        Print this message\n");
    printf("  -a        Omit check for valid team members\n");
    printf("  -r <n>    Give uniform weight of n for all problems\n");
    printf("  -v <n>    Set verbosity to level n\n");
    printf("               n=0: Only give final scores\n");
    printf("               n=1: Also report individual correctness scores (default)\n");
    exit(1);
}



/************** 
 * main routine 
 **************/

int main(int argc, char *argv[])
{
    int verbose_level = 1;
    int errors;
    int team_check = 1;
    char c;

    /* parse command line args */
    while ((c = getopt(argc, argv, "hagv:f:e:r:")) != -1)
        switch (c) {
        case 'h': /* help */
	    usage(argv[0]);
	    break;
        case 'a': /* Don't check team structure */
	    team_check = 0;
	    break;
        case 'g': /* grading summary */
	    grade = 1;
	    break;
        case 'v': /* set verbosity level */
	    verbose_level = atoi(optarg);
	    if (verbose_level < 0 || verbose_level > 1)
		usage(argv[0]);
	    break;
	case 'f': /* test only one function */
	    test_fname = strdup(optarg);
	    break;
	case 'e': /* set error limit */
	    error_limit = atoi(optarg);
	    if (error_limit < 0)
		usage(argv[0]);
	    break;
	case 'r': /* set global rating for each problem */
	    global_rating = atoi(optarg);
	    if (global_rating < 0)
		usage(argv[0]);
	    break;
	default:
	    usage(argv[0]);
    }

    if (grade) {
	error_limit = 0;
	verbose_level = 0;
    }

    if (team_check) {
	/* Students must fill in their team information */
	if (*team.teamname == '\0') {
	    printf("%s: ERROR.  Please enter your team name in the team struct in bits.c.\n", argv[0]);
	    exit(1);
	} else
	    printf("Team: %s\n", team.teamname);
	if ((*team.name1 == '\0') || (*team.id1 == '\0')) {
	    printf("%s: ERROR. Please complete all team member 1 fields in the team struct.\n", argv[0]);
	    exit(1);
	} 
	else
	    printf("Member 1:\t%s\t%s\n", team.name1, team.id1);

	if (((*team.name2 != '\0') && (*team.id2 == '\0')) ||
	    ((*team.name2 == '\0') && (*team.id2 != '\0'))) { 
	    printf("%s: ERROR.  You must fill in all or none of the team member 2 fields in the team struct.\n", argv[0]);
	    exit(1);
	}
	else if (*team.name2 != '\0')
	    printf("Member 2:\t%s\t%s\n", team.name2, team.id2);

	printf("\n");
    }

    /* test each function */
    errors = run_tests(verbose_level > 0);

    if (!grade) {
	if (errors > 0)
	    printf("%d errors encountered.\n", errors);
	else {
	    printf("All tests passed.\n");
	}
    }

    return 0;
}
/* Testing Code */

#include <limits.h>
int test_tmax(void) {
  return LONG_MAX;
}
int test_isZero(int x) {
  return x == 0;
}
int test_bitAnd(int x, int y)
{
  return x&y;
}
int test_bitXor(int x, int y)
{
  return x^y;
}
int test_isEqual(int x, int y)
{
  return x == y;
}
int test_evenBits(void) {
  int result = 0;
  int i;
  for (i = 0; i < 32; i+=2)
    result |= 1<<i;
  return result;
}







int test_reverseBytes(int x)
{
  union U {
    int result;
    char byte[4];
  };
  union U u;
  int temp;
  u.result = x;
  temp = u.byte[0];
  u.byte[0] = u.byte[3];
  u.byte[3] = temp;
  temp = u.byte[1];
  u.byte[1] = u.byte[2];
  u.byte[2] = temp;
  return u.result;
}
Edited by jralexander137 because: n/a
Member Avatar for jralexander137

I've worked out bitAnd and isEqual on paper and they should work but they don't when coded.

isEqual

return (~x & y) >> 3;

bitAnd

(~((~(x | (~y)) | ((~x) | y))) << 1
Member Avatar for jralexander137

Added template code for methods looks like you need in order to compile btest.

/* 
 * CS:APP Data Lab 
 * 
 * bits.c - Source file with your solutions to the Lab.
 *          This is the file you will hand in to your instructor.
 *
 * WARNING: Do not include the <stdio.h> header; it confuses the dlc
 * compiler. You can still use printf for debugging without including
 * <stdio.h>, although you might get a compiler warning. In general,
 * it's not good practice to ignore compiler warnings, but in this
 * case it's OK.  
 */

#include "btest.h"
#include <limits.h>

/*
 * Instructions to Students:
 *
 * STEP 1: Fill in the following struct with your identifying info.
 */
team_struct team =
{
   /* Team name: Replace with either:
      Your login ID if working as a one person team
      or, ID1+ID2 where ID1 is the login ID of the first team member
      and ID2 is the login ID of the second team member */
    "jalexanb",
   /* Student name 1: Replace with the full name of first team member */
   "Jacob Alexander",
   /* Login ID 1: Replace with the login ID of first team member */
   "jalexanb",

   /* The following should only be changed if there are two team members */
   /* Student name 2: Full name of the second team member */
   "",
   /* Login ID 2: Login ID of the second team member */
   ""
};

#if 0
/*
 * STEP 2: Read the following instructions carefully.
 */

You will provide your solution to the Data Lab by
editing the collection of functions in this source file.

CODING RULES:
 
  Replace the "return" statement in each function with one
  or 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 to
  one 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.
 */
/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {


    return (1 << 31)-1;
}


/*
 * isZero - returns 1 if x == 0, and 0 otherwise 
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x) {

//FINISHED.

  return (x==0) >> 31;//!(x!=0);

}
/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(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
 */
int bitXor(int x, int y) {
  return ~((~((~y)&x))&(~((~x)&y)));
}
/* 
 * isEqual - return 1 if x == y, and 0 otherwise 
 *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int isEqual(int x, int y) {
  return (~x & y) >> 3;//~(x ^ (~y)) >> 1;
}
/* 
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int evenBits(void) {
  return 2;
}
/* 
 * reverseBytes - reverse the bytes of x
 *   Example: reverseBytes(0x01020304) = 0x04030201
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int reverseBytes(int x) {
  return 2;
}
Member Avatar for jralexander137

SOLVED.

Thanks everyone for your help with those concepts! All your input and advice really helped me! THANK YOU! <3! No homo. :)

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.