Discretizing raw features into bucketized attributes is a common step before sharing a dataset. However, this process can inadvertently introduce bias and amplify unfairness in downstream tasks. In this paper, we address this issue by formulating the unbiased binning problem, which seeks bucketized attributes that satisfy group parity. We develop an efficient dynamic programming algorithm to solve this problem for equal-size binning. In practice, however, an unbiased binning may incur a high price of fairness or may not exist at all, particularly when group distributions differ substantially. To accommodate settings in which small deviations from perfect parity are acceptable, we introduce the epsilon-biased binning problem, which restricts group disparities across buckets to at most epsilon. We first present a dynamic programming algorithm, DP, that computes the optimal solution in quadratic time. While polynomial, DP does not scale to large datasets. To address this, we propose a practically scalable algorithm based on local search (LS) for epsilon-biased binning. A central component of LS is a divide-and-conquer algorithm (D&C) that quickly finds a solution in near-linear time. We prove that D&C always returns a valid solution whenever one exists. The LS algorithm then initiates a local search, using the D&C solution as the upper bound, to find the optimal solution. Our LS and D&C algorithms are general, and not limited to equal-size binning. To complement our theoretical analysis, we conduct extensive experiments on real-world and synthetic datasets. Besides confirming the efficiency of the algorithms, our experiments verify that while fairness-unaware binning can generate biased attribute representations, this bias can be significantly reduced at a negligible price of fairness.