My Stuff

Tuesday, January 15, 2019

Fast String Reversal

#include <iostream>
#include <cstring>

template<typename T>
void swap(T &c1, T &c2)
{
    // buffer-less swap
    c1 ^= c2;
    c2 ^= c1;
    c1 ^= c2;

}



void reverse(char *s)
{
    if (s == nullptr || *s == '\0')
        return;

    for(auto rear = s + strlen(s) - 1; rear > s; ++s, --rear)
    {
        swap(*s, *rear);
    }
}



int main()
{
    char s[] = "The quick brown fox jumps over the lazy dog";

    std::cout << "Original string: " << s << std::endl;
    reverse(s);

    std::cout << "Reversed string: " << s << std::endl;
    reverse(s);

    std::cout << "2-Reversed string: " << s << std::endl;
    return 0;
}

Prime Number checking of Fibonacci sequence Number

// (c) 2019, Lutfi Shihab


#include <iostream>
#include <vector>

// todo
template <typename T>
class Matrix
{

public:
    Matrix(int rows, int cols) : m_rows(rows), m_cols(cols) {}
    
private:
    int m_rows;
    int m_cols;
};

 
/* function that returns nth Fibonacci number */
template <typename T>
class Fibonacci
{
public:
    Fibonacci(T n) { m_fibNum = fib(n); }
    operator T() const { return m_fibNum; }
    operator int() const { return m_fibNum; }
    
    friend std::ostream& operator<<(std::ostream& os, Fibonacci<T>&  f)
    {
        return os << f.m_fibNum;
    }
    
    Fibonacci<T> operator+=(int k) { return m_fibNum += k; }
    Fibonacci<T> operator %(int k) { return m_fibNum % k; }
    Fibonacci<T> operator /(int k) { return m_fibNum / k; }
    bool         operator<=(int k) { return m_fibNum < k; }
    bool         operator >(int k) { return m_fibNum > k; }
    bool         operator==(int k) { return m_fibNum == k; }

 private:
    void multiply(T F[2][2], T M[2][2])
    {
        T x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
        T y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
        T z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
        T w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
  
        F[0][0] = x; 
        F[0][1] = y; 
        F[1][0] = z; 
        F[1][1] = w;
    }

    /* Optimized version of power() */
    void power(T F[2][2], T n)
    {

        if( n == 0 || n == 1) 
            return; 
        T M[2][2] = {{1,1},{1,0}}; 
  
        this->power(F, n/2); 
        multiply(F, F); 
  
        if (n%2 != 0) 
        multiply(F, M); 
    }

    T fib(T n) 
    { 
        T F[2][2] = {{1,1},{1,0}}; 
        if (n == 0) 
        {
            return 0;
        }
        power(F, n-1); 
  
        return F[0][0]; 
    } 


    T       m_fibNum;
};

  

// Returns n! (the factorial of n)
int Factorial(int n) 
{
    int result = 1;
    for (int i = 1; i <= n; i++) 
    {
        result *= i;
    }

    return result;
}


// Returns true if n is a prime number
template<typename T>
bool IsPrime(T n) 
{
  // Trivial case 1: small numbers
    if (n <= 1) return false;

    // Trivial case 2: even numbers
    if (n % 2 == 0) return n == 2;

    // Now, we have that n is odd and n >= 3.

    // Try to divide n by every odd number i, starting from 3
    for (T i = 3; ; i += 2) 
    {
        // We only have to try i up to the squre root of n
        if (i > n/i) break;

        // Now, we have i <= n/i < n.
        // If n is divisible by i, n is not prime.
        if (n % i == 0) return false;
    }

    // n has no integer factor in the range (1, n), and thus is prime.
    return true;
}



int main()
{
    for(int i=0; i<300; ++i)
    {
        Fibonacci<unsigned long> f(i);
        if (IsPrime(f))
        {
            std::cout << f << " is a prime number\n";
        }
    }
}

Friday, November 30, 2018

I bought this very cheap 8-input signal analyzer sometime ago on E-Bay, but since then never had time to use it, mostly due to the driver available was for Windows only. But a few days ago, I plugged it in on my Linux Mint and googled based on VID I found, I stumbled upon a cool opensource project called "SigOk", a complete project to support various embedded instruments, including my signal analyzer. It comes with a nice GUI front-end called "PulseView".

Operator Overloading in C++

// Assignment operators:
Type &operator&=(Type &lhs, const Type &rhs); // Assign bitwise and
Type &operator^=(Type &lhs, const Type &rhs); // Assign exclusive or
Type &operator|=(Type &lhs, const Type &rhs); // Assign bitwise or
Type &operator-=(Type &lhs, const Type &rhs); // Assign difference
Type &operator<<=(Type &lhs, const Type &rhs); // Assign left shift
Type &operator*=(Type &lhs, const Type &rhs); // Assign product
Type &operator/=(Type &lhs, const Type &rhs); // Assign quotient
Type &operator%=(Type &lhs, const Type &rhs); // Assign remainder
Type &operator>>=(Type &lhs, const Type &rhs); // Assign right shift
Type &operator+=(Type &lhs, const Type &rhs); // Assign sum

//Other modification operators
Type &operator--(Type &lhs); // Prefix decrement - decrement and return new value
Type operator--(Type &lhs, int unused); // Postfix decrement - decrement and return copy of old value
Type &operator++(Type &lhs); // Prefix increment - increment and return new value
Type operator++(Type &lhs, int unused); // Postfix increment - increment and return copy of old value

//Comparison operators
bool operator==(const Type &lhs, const Type &rhs); // Equal
bool operator>(const Type &lhs, const Type &rhs); // Greater than
bool operator>=(const Type &lhs, const Type &rhs); // Greater than or equal
bool operator<(const Type &lhs, const Type &rhs); // less than
bool operator<=(const Type &lhs, const Type &rhs); // less than or equal
bool operator!(const Type &lhs); // logical complement
bool operator!=(const Type &lhs, const Type &rhs); // no equal

//Other operators
Type operator+(const Type &lhs, const Type &rhs); // Addition
Type operator+(const Type &lhs); // Unary plus
Type operator-(const Type &lhs, const Type &rhs); // Subtraction
Type operator-(const Type &lhs); // Unary minus
ContainedType* operator&(const Type &lhs); // Address of
Type operator&(const Type &lhs, const Type &rhs); // Bitwise and
Type operator~(const Type &lhs, const Type &rhs); // Bitwise complement
Type operator^(const Type &lhs, const Type &rhs); // Bitwise exclusive or
Type operator|(const Type &lhs, const Type &rhs); // Bitwise or
Type operator/(const Type &lhs, const Type &rhs); // Division
Type operator<<(const Type &lhs, const Type &rhs); // Left shift
Type operator*(const Type &lhs, const Type &rhs); // Multiplication
ContainedType &operator*(const Type &lhs); // Dereference
Type operator%(const Type &lhs, const Type &rhs); // Remainder
Type operator>>(const Type &lhs, const Type &rhs); // Right shift

class Type
{
// Overloads which must be member functions
ContainedType &operator[](const IndexType &index); // Array subscript
Type &operator=(const Type &rhs); // Assignment
ContainedType &operator->*(); // Member reference
const ContainedType &operator->*() const; // Member reference
ContainedType &operator->(); // Member reference
const ContainedType &operator->() const; // Member reference

// Assignment operators
Type &operator&=(const Type &rhs); // Assign bitwise and
Type &operator^=(const Type &rhs); // Assign exclusive or
Type &operator|=(const Type &rhs); // Assign bitwise or
Type &operator-=(const Type &rhs); // Assign difference
Type &operator<<=(const Type &rhs); // Assign left shift
Type &operator*=(const Type &rhs); // Assign product
Type &operator/=(const Type &rhs); // Assign quotient
Type &operator%=(const Type &rhs); // Assign remainder
Type &operator>>=(const Type &rhs); // Assign right shift
Type &operator+=(const Type &rhs); // Assign sum

//Other modification operators
Type &operator--(Type &lhs); // Prefix decrement - decrement and return new value
Type operator--(Type &lhs, int unused); // Postfix decrement - decrement and return copy of old value
Type &operator++(); // Prefix increment - increment and return new value
Type operator++(int unused); // Postfix increment - increment and return copy of old value

//Comparison operators
bool operator==(const Type &rhs) const; // Equal
bool operator>(const Type &rhs) const; // Greater than
bool operator>=(const Type &rhs) const; // Greater than or equal
bool operator<(const Type &rhs) const; // Less than
bool operator<=(const Type &rhs) const; // Less than or equal
bool operator!=(const Type &rhs) const; // Not equal

//Other operators
Type operator+(const Type &rhs) const; // Addition
Type operator+() const; // Unary plus
Type operator-(const Type &rhs) const; // Subtraction
Type operator-() const; // Unary minus
ContainedType* operator&(); // Address of
const ContainedType* operator&() const; // Address of
Type operator&(const Type &rhs) const; // Bitwise and
Type operator~(const Type &rhs) const; // Bitwise complement
Type operator^(const Type &rhs) const; // Bitwise exclusive or
Type operator|(const Type &rhs) const; // Bitwise or
ContainedType &operator*(); // Dereference
const ContainedType &operator*() const; // Dereference
Type operator/(const Type &rhs) const; // Division
Type operator<<(const Type &rhs) const; // Left shift
bool operator!() const; // Logical complement
Type operator*(const Type &rhs) const; // Multiplication
Type operator%(const Type &rhs) const; // Remainder
Type operator>>(const Type &rhs) const; // Right shift
};

Example

Type& Type::operator = (Type const & rhs)

{

if (&rhs != this)

{

// perform assignment to the class T's attributes

}

// return by reference

return *this;

}

Type Type::operator &= (Type const & rhs)

{

return *this = (*this) & rhs;

}

Type Type::operator & (Type const & rhs)

{

Type newObjVal;

// do customized bitwise AND for the type against rhs

….

// return an object by value

return newObjVal;

}

Type& Type::operator++() // prefix

{

++m_data;

return *this;

}

class MyClass

{

public:

// conversion operator, so expression like: Type b = myClass;

operator Type() { return *m_ptr; }

...

private:

int m_data;

Type m_ptr;

};

MyClass& MyClass::operator++(int unused) // postfix

{

MyClassresult = *this;

++m_data;

// return value before increment

return result;

}

T* MyClass::operator->() const {return m_ptr; }

// Conversion operator

Tuesday, August 14, 2018

Pointers of String

It is always tricky dealing with string in C/C++, but if we know the rule of evaluation of expression in C++, it's not that hard to understand it.

A string declaration is always evaluated from right to left. For example, "char *str" is evaluated as "a variable with name 'str' is a pointer (*) of type char".

Another example:

"const char *str" is evaluated as variable str as a pointer of type char that is const (the content is immutable"). (Please remember, "const char .." expression is identical to expression "char const ...")

"char * const str" is evaluated as a variable with name 'str' is a constant pointer to type char, meaning once the pointer is initialized to point to a string, it cannot be changed to point to another string.

"char const * const str" is evaluated as "a variable with name 'str' is a constant pointer to constant char content. It is a combination to all above.

#include <iostream>

/*

char* str:
const char* str OR char const *str
char* const str:
const char* const str:

*/

#define L(v) #v << " = " << v

using namespace std;

static char cstr[] = "String ini statis!";

int main()
{
char* ps1; // just a regular pointer to a string
ps1 = cstr;
cout << L(ps1) << endl;

#if 0
char const * p_constr = cstr;
// the following causes compile error, as it tries to change value of the static string
*p_constr = '1';
cout << L(p_constr) << endl;
#endif

// a dialect of the above (char const *)
const char* p_constr2 = cstr;
*p_constr2 = '1';
cout << L(p_constr2) << endl;

#if 0
const char* const const_ptr = cstr; // the pointer cannot be set to different one

// the following will cause compile error
const_ptr = cstr2;
cout << L(const_ptr) << std::endl;
#endif
}