Turn biased random number generator into uniform
For general $p$ you can't generate a random bit using a finite number of samples. Indeed, suppose you could do it using $n$ samples. Let $c_k$ be the number of inputs of Hamming weight $k$ which will cause you to return $1$. For your generator to be unbiased, you need
$$ \frac{1}{2} = \sum_{k=0}^n c_k p^k (1-p)^{n-k} = \sum_{\ell=0}^n \left(\sum_{k=\ell}^n c_k (-1)^{\ell-k} \binom{n-k}{\ell-k} \right) p^\ell. $$
If $p$ is transcendental or of the form $a/b$ for odd $b$ then the equation $\frac{1}{2} = \sum_{\ell=0}^n d_\ell p^\ell$ has no integer solutions $d_0,\ldots,d_n$. In particular, even if you know $p$, then in these cases no finite number of samples can be used to extract even one uniformly random bit.

The standard solution, attributed (IIRC) to von Neumann, is to use the following algorithm:


Repeatedly sample two biased samples $r_1,r_2$ until $r_1 \neq r_2$.
Return $r_1$.


Conditioned on $r_1 \neq r_2$, the two outcomes $(r_1,r_2)=(0,1)$ and $(r_1,r_2)=(1,0)$ have the same probability, and so the result is an unbiased bit.

How efficient is this generator? The probability that $r_1 \neq r_2$ is $2p(1-p)$, and so on average you will need $1/(2p(1-p))$ samples per bit. Compare that to the optimal extractor given by Shannon's source coding theorem: extracting $n$ bits should take $n/H(p) + o(n)$ samples with high probability (when $p$ is known).



The plot shows that the von Neumann algorithm is reasonably good but not optimal.