Kiểm tra số chẵn, số lẻ bằng phép thao tác bit trên c++

Với một người không rành máy móc thì hẳn họ cũng sẽ biết rằng máy tính hoạt động theo nguyên tắc của hệ nhị phân (0 và 1). Các phép thao tác bit (bit-wise operations) trong C++ là một thứ khá hay ho để ta có thể vận dụng hệ nhị phân để giải quyết một số bài toán lập trình, mà chủ đề hôm nay sẽ là về kiểm tra tính chẵn lẻ của một số bất kỳ.

Thuật toán kiểm tra cơ bản rất dễ hiểu. Ta thử xem liệu số n nào đó có chia hết cho 2 hay không: nếu chia hết thì số đó là số chẵn, ngược lại là số lẻ.

Với các thao tác bit, ta sẽ ghép n với số 1 bằng toán tử AND. Toán tử AND sẽ chỉ trả về 1 nếu cả hai bit đầu vào đều là 1, đúng theo bảng chân trị của lý thuyết toán rời rạc. Khi một số lẻ ở hệ thập phân được chuyển đổi sang hệ nhị phân, chữ số cuối cùng sẽ luôn là số 1. Lợi dụng điều này, ta sẽ biết được số n ban đầu là lẻ hay chẵn bằng cách xem xét output của AND.

Ưu điểm của thao tác bit là nó chạy nhanh hơn cách thông thường, với lại làm bạn ngầu hơn với cả những người đã biết lập trình (haha).

Sau đây là đoạn code C++ mô phỏng lại những gì mình vừa nói.

#include <bits/stdc++.h>
using namespace std;
int main(){
     int n = 7;
     if (n & 1){
           cout << "odd number.";
     } //& là ký hiệu của phép AND trên C++.
     else cout << "even number.";
}

Một bài lập trình hay về số nguyên tố

Số nguyên tố là thứ quá đỗi quen thuộc với những ai học toán, cũng như đối với các lập trình viên. Ai học giải thuật đều đã giải qua những bài về số nguyên tố, với độ khó dàn trải từ đơn giản tới phức tạp, từ vòng lặp thử tính chia hết tới sàng số nguyên tố Eratosthene…

Hôm nay mình rảnh thì có nghĩ ra một bài như thế này, các bạn xem qua nhé!

Đề bài: Cho hai số nguyên dương x và y (các test case đưa vào luôn đảm bảo x > y). Viết chương trình kiểm tra xem x2 – y2 có phải là số nguyên tố hay không.

Thoạt nhìn qua thì bài này khá đơn giản. Tính x2 – y2, rồi kiểm tra. Nhưng khi x và y lớn, ví dụ cỡ 1018 thì cách này sẽ chạy quá thời gian.

Hãy quan sát biểu thức x2 – y2. Nếu bạn đã học 7 hằng đẳng thức đáng nhớ, sẽ dễ thấy rằng x2 – y2 có thể được viết dưới dạng (x-y)(x+y). Vì x và y đều là các số nguyên dương, nên x 1 và y 1. Từ đó suy ra: (x+y) 1.

Xét biểu thức còn lại, x-y. Sẽ xảy ra hai trường hợp là (x-y) 1 và (x-y)=1. Với trường hợp đầu tiên, x2 – y2 sẽ không là số nguyên tố vì vi phạm định nghĩa (chỉ có hai ước là 1 và chính nó). Do đó với (x-y)=1, biểu thức ban đầu sẽ tương đương với chỉ x+y. Ta chỉ cần xét x+y là đủ. Sau đây là code miêu tả bài toán này.

bool primeSquare(long long a, long long b)
{
    if (a-b != 1) return false;
    long long num = a + b;
    if (num % 2 == 0) return false;
    for (long long i = 3; i*i <= num; i += 2)
    {
        if (num % i == 0) return false;
    }
    return true;
}

Intuitive explanation to how dividing by 0 is impossible

We all know a random number times 0 always ends up 0, but the division for 0 is impossible. Computer programs return numerous errors upon stumbling across this matter, math leaners try their best with conditions to avoid dividing by 0. Some guys on YouTube even tried to prove that 1 equals to 0 using this very infamous numerical expression.

But why is that? Let us take a very straightforward and intuitive example to explain why dividing by 0 is a meaningless act.

Say you have a delicious cake. Rashford and Pogba come to your house to eat it with you. In order to make everyone happy, the cake must be divided into 3 equal parts, so each one of you will have a third of that cake. In another scenario, it is the same cake, but you celebrate something alone and want to eat the whole thing. Simple. You divide the cake by 1, so it ends up being itself. Bon appetit!

But what happens when you attempt to divide the cake by 0? The cake just disappears. Just a second ago, a delicious piece of culinary art stays in front of you, but now it is in the void. The act itself gets ridiculous when you think about it. Where is the cake? Ask the divisor.

That is the answer for dividing by 0. You cannot destroy matters, because the act of dividing by 0 “destroys” matters and numbers. For those who studied physics, you must be familiar with the Conservation of mass: “mass can neither be created nor destroyed, although it may be rearranged in space, or the entities associated with it may be changed in form.”

Put plots by Matplotlib to your standard

This post provide the modification for python script for plotting using matplotlib.

plt.rcParams['font.family'] = 'Myriad Pro'
plt.rcParams['font.serif'] = 'Myriad Pro'
plt.rcParams['font.monospace'] = 'PragmataPro Mono Liga'
plt.rcParams['font.size'] = 12
plt.rcParams['axes.labelsize'] = 12
plt.rcParams['axes.labelweight'] = 'bold'
plt.rcParams['axes.titlesize'] = 10
plt.rcParams['xtick.labelsize'] = 10
plt.rcParams['ytick.labelsize'] = 10
plt.rcParams['legend.fontsize'] = 10
plt.rcParams['figure.titlesize'] = 12

Lost Desktop icons after uninstalling Komorebi on Linux Mint

Komorebi is an application that enables animations for desktop wallpapers. When uninstall Komorebi, there is a possibility that desktop will become unresponsive: desklets are still displaying but no icons, right click doesn’t show anything. To fix it, run this code in Terminal:

gsettings set org.nemo.desktop show-desktop-icons true

Thing should be fine after this.

Best way to install Node.js and NPM

I’m writing this post as I need to install node.js and npm to install packages for reveal.js, I’m on Ubuntu 18.04 Bionic.

Normally we can install node.js via terminal by

sudo apt install nodejs

But this is not the best way since the version is outdated and some dependencies won’t meet. The best way to install the latest node.js and npm is via nvm.

curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.8/install.sh | bash

Note that the version number can be checked by going directly to the website and see. The above script will download all the package and put nvm into the Linux alias (so we can use the nvm command globally). After this, log out and log in to activate the alias.

Once you log in, run below script

nvm install node

To update:

nvm install node
nvm alias default nodenvm install node
nvm alias default node

From this answer: https://askubuntu.com/a/1009527