非标准库的一些好用的东西

Bit Opearation Built-in Functions

int __builtin_ffs (int x)
//Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. 
int __builtin_clz (unsigned int x)
//Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. 
int __builtin_ctz (unsigned int x)
//Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. 
int __builtin_clrsb (int x)
//Returns the number of leading redundant sign bits in x, i.e. the number of bits following the most significant bit that are identical to it. There are no special cases for 0 or other values.
int __builtin_popcount (unsigned int x)
//Returns the number of 1-bits in x.
int __builtin_parity (unsigned int x)
//Returns the parity of x, i.e. the number of 1-bits in x modulo 2.

O(n)求字符串的最小表示

Problem

求一个字符串的循环移位中字典序最小的那个。

Solution

两个指针指向两个同构串的开头,比较它们的大小,较大的那个串的与另一个串相等的那一部分及其第一个不同的字符不可能是最小同构串开头,可以直接跳过。

Code

int MinimumRepresentation(int *a,int n) {
    ++a;
    int p1=0,p2=1,len=0;
    while(p1<n && p2<n && len<n) {
        if(a[(p1+len)%n]==a[(p2+len)%n])
            len++;
        else {
            (a[(p1+len)%n]>a[(p2+len)%n]?p1:p2)+=len+1;
            if(p1==p2)
                p2++;
            len=0;
        }
    }
    return std::min(p1,p2)+1;
}