Removing duplicates efficiently and with a low memory overhead
Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A[y]$, $y \ge 0$, represents the range $[2^m y, 2^m(y+1)-1]$.  For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits.  Try to store $z$ (not $x$!) at location $y$:


When $A[y]=z$ already, do nothing: $x$ is a duplicate.
When $A[y]$ is uninitialized, store $z$ at $A[y]$.
Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists.  You will have to search linearly through the list headed by $A[y]$ and, depending on what the search uncovers, potentially insert $z$ into the list.


At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short.  When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing.  If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$).  This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it is a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.