#include <stdio.h>
/*
* CS:APP Data Lab
*
* <Adam Nurlign (AndrewID: ain)>
*
* bits.c - Source file with your solutions to the Lab.
* This is the file you will hand in to your instructor.
*/
/* Instructions to Students:
You will provide your solution to the Data Lab by
editing the collection of functions in this source file.
INTEGER 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:
long Funct(long arg1, long arg2, ...) {
// brief description of how your implementation works
long var1 = Expr1;
...
long varM = ExprM;
varJ = ExprJ;
...
varN = ExprN;
return ExprR;
}
Each "Expr" is an expression using ONLY the following:
1. (Long) integer constants 0 through 255 (0xFFL), inclusive. You are
not allowed to use big constants such as 0xffffffffL.
2. Function arguments and local variables (no global variables).
3. Local variables of type int and long
4. Unary integer operations ! ~
- Their arguments can have types int or long
- Note that ! always returns int, even if the argument is long
5. Binary integer operations & ^ | + << >>
- Their arguments can have types int or long
6. Casting from int to long and from long to int
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 other than between int and long.
7. Use any data type other than int or long. This implies that you
cannot use arrays, structs, or unions.
You may assume that your machine:
1. Uses 2s complement representations for int and long.
2. Data type int is 32 bits, long is 64.
3. Performs right shifts arithmetically.
4. Has unpredictable behavior when shifting if the shift amount
is less than 0 or greater than 31 (int) or 63 (long)
EXAMPLES OF ACCEPTABLE CODING STYLE:
//
// pow2plus1 - returns 2^x + 1, where 0 <= x <= 63
//
long pow2plus1(long x) {
// exploit ability of shifts to compute powers of 2
// Note that the 'L' indicates a long constant
return (1L << x) + 1L;
}
//
// pow2plus4 - returns 2^x + 4, where 0 <= x <= 63
//
long pow2plus4(long x) {
// exploit ability of shifts to compute powers of 2
long result = (1L << x);
result += 4L;
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 operations (integer, logical,
or comparison) that you are allowed to use for your implementation
of the function. The max operator count is checked by dlc.
Note that assignment ('=') 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. Use the BDD checker to formally verify your functions
5. 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.
CAUTION:
Do not add an #include of <stdio.h> (or any other C library header)
to this file. C library headers almost always contain constructs
that dlc does not understand. For debugging, you can use printf,
which is declared for you just below. It is normally bad practice
to declare C library functions by hand, but in this case it's less
trouble than any alternative.
dlc will consider each call to printf to be a violation of the
coding style (function calls, after all, are not allowed) so you
must remove all your debugging printf's again before submitting your
code or testing it with dlc or the BDD checker. */
extern int printf(const char *, ...);
/* Edit the functions below. Good luck! */
// 2
/*
* copyLSB - set all bits of result to least significant bit of x
* Examples:
* copyLSB(5L) = 0xFFFFFFFFFFFFFFFFL,
* copyLSB(6L) = 0x0000000000000000L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
long copyLSB(long x) {
long leastSignificantBit=x&1;
return (leastSignificantBit<<63)>>63;
}
/*
* dividePower2 - Compute x/(2^n), for 0 <= n <= 62
* Round toward zero
* Examples: dividePower2(15L,1L) = 7L, dividePower2(-33L,4L) = -2L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
long dividePower2(long x, long n) {
long highestOrderBit=(x>>63)&1;
return (x>>n)+highestOrderBit;
}
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (least significant) to 7 (most significant)
* Examples: getByte(0x12345678L,1) = 0x56L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
long getByte(long x, long n) {
long mask=0xFF;
long shiftByAmount=n<<3;
long newX=x>>shiftByAmount;
return newX&mask;
}
/*
* anyOddBit - return 1 if any odd-numbered bit in word set to 1
* where bits are numbered from 0 (least significant) to 63 (most significant)
* Examples anyOddBit(0x5L) = 0L, anyOddBit(0x7L) = 1L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 14
* Rating: 2
*/
long anyOddBit(long x) {
long mask=0xAA+(0xAA<<8);
mask=mask+(mask<<16);
mask=mask+(mask<<32);
long temp = x&mask;
return !!temp;
}
// 3
/*
* conditional - same as x ? y : z
* Example: conditional(2,4L,5L) = 4L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
long conditional(long x, long y, long z) {
long sety=!!x; //0 if we should output z and 1 if we should output y
long setz=(~sety)&1; //this is 0 if we should output y and 1 if we should output z
long yTemp=y&((sety<<63)>>63);
long zTemp=z&((setz<<63)>>63);
return yTemp+zTemp;
}
/*
* subtractionOK - Determine if can compute x-y without overflow
* Example: subtractionOK(0x8000000000000000L,0x8000000000000000L) = 1L,
* subtractionOK(0x8000000000000000L,0x7000000000000000L) = 0L,
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
long subtractionOK(long x, long y) {
long xSignBitOn=(x>>63)&1;
long ySignBitOn=(y>>63)&1;
long result=x+(~y+1);
long resultSignBitOn=(result>>63)&1;
long badOne=!xSignBitOn&ySignBitOn&resultSignBitOn;
long badTwo=xSignBitOn&(!ySignBitOn)&(!resultSignBitOn);
return !(badOne+badTwo);
}
/*
* bitMask - Generate a mask consisting of all 1's
* between lowbit and highbit
* Examples: bitMask(5L,3L) = 0x38L
* Assume 0 <= lowbit < 64, and 0 <= highbit < 64
* If lowbit > highbit, then mask should be all 0's
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
long bitMask(long highbit, long lowbit) {
long allOneBit=~0;
long one=1;
long sixtyThree=63;
long allOneBitExceptFirst=allOneBit^(one<<sixtyThree);
long temp=allOneBitExceptFirst>>(63+(~highbit+1)+(~1+1));
long result=temp&(allOneBit<<lowbit);
return result;
}
/*
* rotateLeft - Rotate x to the left by n
* Can assume that 0 <= n <= 63
* Examples:
* rotateLeft(0x8765432187654321L,4L) = 0x7654321876543218L
* Legal ops: ~ & ^ | + << >> !
* Max ops: 25
* Rating: 3
*/
long rotateLeft(long x, long n) {
long temp1=x<<n;
long temp2=x>>(63+(~n+1)+1);
long zero=0;
long one=1;
long sixtyThree=63;
long allOneBit=~zero;
long allOneBitExceptFirst=allOneBit^(one<<sixtyThree);
long temp3=allOneBitExceptFirst>>(63+(~n+1));
long temp4= temp2&temp3;
return temp1+temp4;
}
// 4
/*
* trueFiveEighths - multiplies by 5/8 rounding toward 0,
* avoiding errors due to overflow
* Examples:
* trueFiveEighths(11L) = 6L
* trueFiveEighths(-9L) = -5L
* trueFiveEighths(0x3000000000000000L) = 0x1E00000000000000L (no overflow)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
long trueFiveEighths(long x) {
return 2L;
}
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5L) = 2, bitCount(7L) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 50
* Rating: 4
*/
long bitCount(long x) {
long returnValue=0;
returnValue+=x&1;
returnValue+=(x>>1)&1;
returnValue+=(x>>2)&1;
returnValue+=(x>>3)&1;
returnValue+=(x>>4)&1;
returnValue+=(x>>5)&1;
returnValue+=(x>>6)&1;
returnValue+=(x>>7)&1;
returnValue+=(x>>8)&1;
returnValue+=(x>>9)&1;
returnValue+=(x>>10)&1;
returnValue+=(x>>11)&1;
returnValue+=(x>>12)&1;
returnValue+=(x>>13)&1;
returnValue+=(x>>14)&1;
returnValue+=(x>>15)&1;
returnValue+=(x>>16)&1;
returnValue+=(x>>17)&1;
returnValue+=(x>>18)&1;
returnValue+=(x>>19)&1;
returnValue+=(x>>20)&1;
returnValue+=(x>>21)&1;
returnValue+=(x>>22)&1;
returnValue+=(x>>23)&1;
returnValue+=(x>>24)&1;
returnValue+=(x>>25)&1;
returnValue+=(x>>25)&1;
returnValue+=(x>>27)&1;
returnValue+=(x>>28)&1;
returnValue+=(x>>29)&1;
returnValue+=(x>>30)&1;
returnValue+=(x>>31)&1;
returnValue+=(x>>32)&1;
returnValue+=(x>>33)&1;
returnValue+=(x>>34)&1;
returnValue+=(x>>35)&1;
returnValue+=(x>>36)&1;
returnValue+=(x>>37)&1;
returnValue+=(x>>38)&1;
returnValue+=(x>>39)&1;
returnValue+=(x>>40)&1;
returnValue+=(x>>41)&1;
returnValue+=(x>>42)&1;
returnValue+=(x>>43)&1;
returnValue+=(x>>44)&1;
returnValue+=(x>>45)&1;
returnValue+=(x>>46)&1;
returnValue+=(x>>47)&1;
returnValue+=(x>>48)&1;
returnValue+=(x>>49)&1;
returnValue+=(x>>50)&1;
returnValue+=(x>>51)&1;
returnValue+=(x>>52)&1;
returnValue+=(x>>53)&1;
returnValue+=(x>>54)&1;
returnValue+=(x>>55)&1;
returnValue+=(x>>56)&1;
returnValue+=(x>>57)&1;
returnValue+=(x>>58)&1;
returnValue+=(x>>59)&1;
returnValue+=(x>>60)&1;
returnValue+=(x>>61)&1;
returnValue+=(x>>62)&1;
returnValue+=(x>>63)&1;
return returnValue;
}
/*
* bitParity - returns 1 if x contains an odd number of 0's
* Examples: bitParity(5L) = 0L, bitParity(7L) = 1L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 22
* Rating: 4
*/
long bitParity(long x) {
long returnValue=0;
returnValue+=x&1;
returnValue+=(x>>1)&1;
returnValue+=(x>>2)&1;
returnValue+=(x>>3)&1;
returnValue+=(x>>4)&1;
returnValue+=(x>>5)&1;
returnValue+=(x>>6)&1;
returnValue+=(x>>7)&1;
returnValue+=(x>>8)&1;
returnValue+=(x>>9)&1;
returnValue+=(x>>10)&1;
returnValue+=(x>>11)&1;
returnValue+=(x>>12)&1;
returnValue+=(x>>13)&1;
returnValue+=(x>>14)&1;
returnValue+=(x>>15)&1;
returnValue+=(x>>16)&1;
returnValue+=(x>>17)&1;
returnValue+=(x>>18)&1;
returnValue+=(x>>19)&1;
returnValue+=(x>>20)&1;
returnValue+=(x>>21)&1;
returnValue+=(x>>22)&1;
returnValue+=(x>>23)&1;
returnValue+=(x>>24)&1;
returnValue+=(x>>25)&1;
returnValue+=(x>>26)&1;
returnValue+=(x>>27)&1;
returnValue+=(x>>28)&1;
returnValue+=(x>>29)&1;
returnValue+=(x>>30)&1;
returnValue+=(x>>31)&1;
returnValue+=(x>>32)&1;
returnValue+=(x>>33)&1;
returnValue+=(x>>34)&1;
returnValue+=(x>>35)&1;
returnValue+=(x>>36)&1;
returnValue+=(x>>37)&1;
returnValue+=(x>>38)&1;
returnValue+=(x>>39)&1;
returnValue+=(x>>40)&1;
returnValue+=(x>>41)&1;
returnValue+=(x>>42)&1;
returnValue+=(x>>43)&1;
returnValue+=(x>>44)&1;
returnValue+=(x>>45)&1;
returnValue+=(x>>46)&1;
returnValue+=(x>>47)&1;
returnValue+=(x>>48)&1;
returnValue+=(x>>49)&1;
returnValue+=(x>>50)&1;
returnValue+=(x>>51)&1;
returnValue+=(x>>52)&1;
returnValue+=(x>>53)&1;
returnValue+=(x>>54)&1;
returnValue+=(x>>55)&1;
returnValue+=(x>>56)&1;
returnValue+=(x>>57)&1;
returnValue+=(x>>58)&1;
returnValue+=(x>>59)&1;
returnValue+=(x>>60)&1;
returnValue+=(x>>61)&1;
returnValue+=(x>>62)&1;
returnValue+=(x>>63)&1;
long numberOfZeroes=64-returnValue;
long isOddNumberZeroes=numberOfZeroes&1;
return isOddNumberZeroes;
}
int main()
{
printf("%li",bitCount(0x8d1b45f21a369000));
} Write, Run & Share C Language code online using OneCompiler's C online compiler for free. It's one of the robust, feature-rich online compilers for C language, running the latest C version which is C18. Getting started with the OneCompiler's C editor is really simple and pretty fast. The editor shows sample boilerplate code when you choose language as 'C' and start coding!
OneCompiler's C online editor supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample C program which takes name as input and print your name with hello.
#include <stdio.h>
int main()
{
char name[50];
printf("Enter name:");
scanf("%s", name);
printf("Hello %s \n" , name );
return 0;
}
C language is one of the most popular general-purpose programming language developed by Dennis Ritchie at Bell laboratories for UNIX operating system. The initial release of C Language was in the year 1972. Most of the desktop operating systems are written in C Language.
When ever you want to perform a set of operations based on a condition if-else is used.
if(conditional-expression) {
// code
} else {
// code
}
You can also use if-else for nested Ifs and if-else-if ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to if-else-if ladder.
switch(conditional-expression) {
case value1:
// code
break; // optional
case value2:
// code
break; // optional
...
default:
// code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
// code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while(condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Array is a collection of similar data which is stored in continuous memory addresses. Array values can be fetched using index. Index starts from 0 to size-1.
data-type array-name[size];
data-type array-name[size][size];
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity.
Two types of functions are present in C
Library functions are the in-built functions which are declared in header files like printf(),scanf(),puts(),gets() etc.,
User defined functions are the ones which are written by the programmer based on the requirement.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
//code
}