JXNVCE ALGO-LOG YouJin Jung

ROTATE-BITS

22 Dec 2021

FW 단에서 중요한 bit shifting strategy

#include <bits/stdc++.h>
using namespace std;
 
#define SHORT_SIZE 16

unsigned short leftRotate(unsigned short x, short d) {
    return (x << d) | (x >> (SHORT_SIZE - d));
}
 
unsigned short rightRotate(unsigned short x, short d) {
    return (x >> d) | (x << (SHORT_SIZE - d));
}

int main() {
    unsigned short n = 28;
    short d = 2;
 
    cout << leftRotate(n, d) << endl;
    cout << rightRotate(n, d) << endl;
 
    return 0;
}

REVERSE-BITS-STANDARD

21 Dec 2021

C를 이용한 Bit reversion

#include <bits/stdc++.h>

unsigned int reverseBits(unsigned int num) {
    unsigned int  NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0, i, temp;
  
    for (i = 0; i < NO_OF_BITS; i++) {
        temp = (num & (1 << i));
        if(temp)
            reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
    }
   
    return reverse_num;
}
  
int main() {
    unsigned int x = 2; 
    printf("%u", reverseBits(x));
    getchar();
}

ITERATIVE-TOWER-OF-HANOI

23 Nov 2021 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
struct Stack {
  unsigned capacity;
  int top;
  int *array;
};

struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack -> capacity = capacity;
    stack -> top = -1;
    stack -> array = (int*) malloc(stack -> capacity * sizeof(int));
    return stack;
}
 
int isFull(struct Stack* stack){
  return (stack->top == stack->capacity - 1);
}
 
int isEmpty(struct Stack* stack) {
  return (stack->top == -1);
}
 
void push(struct Stack *stack, int item) {
    if (isFull(stack))
        return;
    stack -> array[++stack -> top] = item;
}

int pop(struct Stack* stack) {
    if (isEmpty(stack))
        return INT_MIN;
    return stack -> array[stack -> top--];
}

void moveDisk(char fromPeg, char toPeg, int disk) {
    cout <<"Move the disk " << disk <<" from " << fromPeg << " to "<< toPeg << endl;
}
 

void moveDisksBetweenTwoPoles(struct Stack *src, struct Stack *dest, char s, char d){
    int pole1TopDisk = pop(src);
    int pole2TopDisk = pop(dest);
 
    if (pole1TopDisk == INT_MIN) {
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
 
    else if (pole2TopDisk == INT_MIN) {
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
 
    else if (pole1TopDisk > pole2TopDisk) {
        push(src, pole1TopDisk);
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }

    else {
        push(dest, pole2TopDisk);
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
}
 
void tohIterative(int num_of_disks, struct Stack *src, struct Stack *aux, struct Stack *dest) {
    int i, total_num_of_moves;
    char s = 'S', d = 'D', a = 'A';
    if (num_of_disks % 2 == 0) {
        char temp = d;
        d = a;
        a = temp;
    }
    total_num_of_moves = pow(2, num_of_disks) - 1;
    for (i = num_of_disks; i >= 1; i--)
        push(src, i);
    for (i = 1; i <= total_num_of_moves; i++) {
        if (i % 3 == 1) moveDisksBetweenTwoPoles(src, dest, s, d);
        else if (i % 3 == 2) moveDisksBetweenTwoPoles(src, aux, s, a);
        else if (i % 3 == 0) moveDisksBetweenTwoPoles(aux, dest, a, d);
    }
}

int main() {
    unsigned num_of_disks = 3;
    struct Stack *src, *dest, *aux;

    src = createStack(num_of_disks);
    aux = createStack(num_of_disks);
    dest = createStack(num_of_disks);
 
    tohIterative(num_of_disks, src, aux, dest);
    return 0;
}

GFG-MEDIAN-OF-TWO-SORTED-ARRAYS

22 Nov 2021 
#include <bits/stdc++.h>
using namespace std;

int getMedian(int ar1[],int ar2[], int n) {
    int i = 0; 
    int j = 0; 
    int count;
    int m1 = -1, m2 = -1;

    for (count = 0; count <= n; count++) {
        if (i == n) {
            m1 = m2;
            m2 = ar2[0];
            break;
        }

        else if (j == n) {
            m1 = m2;
            m2 = ar1[0];
            break;
        }

        if (ar1[i] <= ar2[j]) {
            m1 = m2;
            m2 = ar1[i];
            i++;
        }
        else {
            m1 = m2;
            m2 = ar2[j];
            j++;
        }
    }
 
    return (m1 + m2)/2;
}
 
int main() {
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
 
    int n1 = sizeof(ar1) / sizeof(ar1[0]);
    int n2 = sizeof(ar2) / sizeof(ar2[0]);
    if (n1 == n2)
        cout << "Median is " << getMedian(ar1, ar2, n1) ;
    else
        cout << "Doesn't work for arrays" << " of unequal size" ;
    getchar();
    return 0;
}

GFG-GOLOMB-SEQUENCE

19 Nov 2021

Golomb sequence with recursion

a(1) = 1 
a(n + 1) = 1 + a(n + 1 – a(a(n)))

#include <bits/stdc++.h>
using namespace std;

int findGolomb(int n) {
    if (n == 1) return 1;
        
    return 1 + findGolomb(n - findGolomb(findGolomb(n - 1)));
}
 
void printGolomb(int n) {
    for (int i = 1; i <= n; i++)
        cout << findGolomb(i) << " ";
}

int main() {
    int n = 9;
    printGolomb(n);
    return 0;
}