Task 3 Largest PO2 LE: Implement the largest_po2_le function as directed in the comment above the function. If the directions are unclear, run the code, and look at the expected answer for a few inputs. As specified in the comment, you may not use multiplication or some sort of power function, and should instead rely on bitwise operations. Consider how binary numbers are structured, and how you might find the largest power of 2 of a binary number.
Task 3 Largest PO2 LE:
Implement the largest_po2_le function as directed in the comment above the function. If the directions are unclear, run the code, and look at the expected answer for a few inputs.
As specified in the comment, you may not use multiplication or some sort of power function, and should instead rely on bitwise operations. Consider how binary numbers are structured, and how you might find the largest power of 2 of a binary number.
Code:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// BEGIN STRINGBUILDER IMPLEMENTATION
// This code is a very rudimentary stringbuilder-like implementation
// To create a new stringbuilder, use the following line of code
//
// stringbuilder sb = new_sb();
//
// If you want to append a character to the stringbuilder, use the
// following line of code. Replace whatever character you want to
// append where the 'a' is.
//
// sb_append_char(sb, 'a');
//
// Though there are some other functions that might be useful to you,
// the driver code provided uses the functions, so there is no need
// to use them manually.
typedef struct {
char** cars;
size_t* len;
size_t* alloc_size;
} stringbuilder;
stringbuilder new_sb() {
stringbuilder sb;
sb.cars = malloc(sizeof(char*));
*sb.cars = malloc(8*sizeof(char));
(*sb.cars)[0] = 0;
sb.len = malloc(sizeof(size_t));
*sb.len = 0;
sb.alloc_size = malloc(sizeof(size_t));
*sb.alloc_size = 8;
return sb;
}
void sb_append(stringbuilder sb, char a) {
int len = *sb.len;
if (len >= (*sb.alloc_size)-1) {
*sb.alloc_size = (*sb.alloc_size)*2;
char* newcars = malloc((*sb.alloc_size)*sizeof(char));
for (int i = 0; i < *sb.len; i++) {
newcars[i] = (*sb.cars)[i];
}
free(*sb.cars);
(*sb.cars) = newcars;
}
(*sb.cars)[len] = a;
len++;
(*sb.cars)[len] = 0;
*sb.len = len;
}
void delete_sb(stringbuilder sb) {
free(*sb.cars);
free(sb.cars);
free(sb.len);
free(sb.alloc_size);
}
bool sb_is_equal(stringbuilder sb1, stringbuilder sb2) {
if (*sb1.len != *sb2.len)
return false;
for (int i = 0; i < *sb1.len; i++) {
if ((*sb1.cars)[i] != (*sb2.cars)[i])
return false;
}
return true;
}
void print_sb(const stringbuilder sb) {
printf("%s", *sb.cars);
}
// END STRINGBUILDER IMPLEMENTATION
// ============================================================
// Write your solutions to the tasks below
const unsigned UNS_MAX = -1; // 1111...
const unsigned UNS_MIN = 0; // 0000...
const int INT_MAX = UNS_MAX >> 1; // 0111...
const int INT_MIN = ~INT_MAX; // 1000...
// Task 1
// For this function, you must return an integer holding the value
// x+1, however you may not use any constants or the symbol '+'
// anywhere in your solution. This means that
//
// return x - (-1);
//
// is not a valid soltion, because it uses the constant -1.
//
// Hint: Consider what internally happens when you do -x.
int plus_one(int x) {
return x;
}
// Task 2
// For this function, you must build a string that when printed,
// will output the entire binary representation of the integer x,
// no matter how many bits an integer is. You may NOT use
// division (/) or mod (%) anywhere in your code, and should
// instead rely on bitwise operations to read the underlying binary
// representation of x.
stringbuilder get_bin_1(int x) {
stringbuilder sb = new_sb();
sb_append(sb, '$');
return sb;
}
// Task 3
// For this function, you must return the largest power of 2 that
// is less than or equal to x (which will be positive). You may
// not use multiplication or some sort of power function to do this,
// and should instead rely on bitwise operations and the underlying
// binary representation of x. If x is 0, then you should return 0.
unsigned largest_po2_le(unsigned x) {
return x;
}
I have implemented the function according to the instructions. Comments are mentioned for better understanding of the implementation. The code is as follows:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// BEGIN STRINGBUILDER IMPLEMENTATION
// This code is a very rudimentary stringbuilder-like implementation
// To create a new stringbuilder, use the following line of code
//
// stringbuilder sb = new_sb();
//
// If you want to append a character to the stringbuilder, use the
// following line of code. Replace whatever character you want to
// append where the 'a' is.
//
// sb_append_char(sb, 'a');
//
// Though there are some other functions that might be useful to you,
// the driver code provided uses the functions, so there is no need
// to use them manually.
typedef struct {
char** cars;
size_t* len;
size_t* alloc_size;
} stringbuilder;
stringbuilder new_sb() {
stringbuilder sb;
sb.cars = malloc(sizeof(char*));
*sb.cars = malloc(8*sizeof(char));
(*sb.cars)[0] = 0;
sb.len = malloc(sizeof(size_t));
*sb.len = 0;
sb.alloc_size = malloc(sizeof(size_t));
*sb.alloc_size = 8;
return sb;
}
void sb_append(stringbuilder sb, char a) {
int len = *sb.len;
if (len >= (*sb.alloc_size)-1) {
*sb.alloc_size = (*sb.alloc_size)*2;
char* newcars = malloc((*sb.alloc_size)*sizeof(char));
for (int i = 0; i < *sb.len; i++) {
newcars[i] = (*sb.cars)[i];
}
free(*sb.cars);
(*sb.cars) = newcars;
}
(*sb.cars)[len] = a;
len++;
(*sb.cars)[len] = 0;
*sb.len = len;
}
void delete_sb(stringbuilder sb) {
free(*sb.cars);
free(sb.cars);
free(sb.len);
free(sb.alloc_size);
}
bool sb_is_equal(stringbuilder sb1, stringbuilder sb2) {
if (*sb1.len != *sb2.len)
return false;
for (int i = 0; i < *sb1.len; i++) {
if ((*sb1.cars)[i] != (*sb2.cars)[i])
return false;
}
return true;
}
void print_sb(const stringbuilder sb) {
printf("%s", *sb.cars);
}
// END STRINGBUILDER IMPLEMENTATION
// ============================================================
// Write your solutions to the tasks below
const unsigned UNS_MAX = -1; // 1111...
const unsigned UNS_MIN = 0; // 0000...
const int INT_MAX = UNS_MAX >> 1; // 0111...
const int INT_MIN = ~INT_MAX; // 1000...
// Task 1
// For this function, you must return an integer holding the value
// x+1, however you may not use any constants or the symbol '+'
// anywhere in your solution. This means that
//
// return x - (-1);
//
// is not a valid soltion, because it uses the constant -1.
//
// Hint: Consider what internally happens when you do -x.
int plus_one(int x) {
return x;
}
// Task 2
// For this function, you must build a string that when printed,
// will output the entire binary representation of the integer x,
// no matter how many bits an integer is. You may NOT use
// division (/) or mod (%) anywhere in your code, and should
// instead rely on bitwise operations to read the underlying binary
// representation of x.
stringbuilder get_bin_1(int x) {
stringbuilder sb = new_sb();
sb_append(sb, '$');
return sb;
}
// Task 3
// For this function, you must return the largest power of 2 that
// is less than or equal to x (which will be positive). You may
// not use multiplication or some sort of power function to do this,
// and should instead rely on bitwise operations and the underlying
// binary representation of x. If x is 0, then you should return 0.
unsigned largest_po2_le(unsigned x) {
long res = 1;
long power;
for (long i = 0; i < UNS_MAX; i++) {
// compute the power of 2
power = 1 << i;
// check if power of 2 is greater the given number
// if yes, then break from loop
if (power>= x) {
break;
}
// otherwise, make the result equal to this power
res = power;
}
return res;
}
int main()
{
printf("%d", largest_po2_le(100));
return 0;
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
