this is my solution with time O(a*n) where a is the length of the integer. I solve the problem by using a counting sort (O(n)) method at each digit of the numbers (start from the lowest digit and thus the order is stable) and gradually locate the position of the single number cauz the singular number makes the count of 0s (or 1s) an odd number at that digit.

```
class Solution {
public:
int singleNumber(int A[], int n){
//the digits of integers
int length=8*sizeof(int);
int count0,count1;
//lookup range
int posp=0,posq=n-1;
//for each digit
for(int i=0;i<length;i++){
if(posp==posq) return A[posp];
//counting 0s and 1s
count0=0;count1=0;
for(int j=posp;j<=posq;j++){
if((A[j]&(1<<i))==0)count0++;
else count1++;
}
//swaping integers with 0s to the front(order stable)
int pos0=posp,curpos=posp;
while(curpos<=posq){
if((A[curpos]&(1<<i))==0){
int temp=A[pos0];
A[pos0]=A[curpos];
A[curpos]=temp;
pos0++;
}
curpos++;
}
//relocate
if(!(count0%2))posp+=count0;
else posq-=count1;
}
return A[posp];
}
};
```