k-Nearest Neighbors (kNN) algorithm is a method to find the closest points in a dataset to a query point. The result of kNN can be used for classification and regression, both of which are commonly used in data mining and machine learning. In this paper, Enhanced Vote Count (EVC) circuit, which uses hardware to compare the quantized projected values of query and training/reference vectors instead of the vectors themselves, is considered to approximate the kNN search to provide a low complexity search solution. To improve the performance of EVC with limited projection number because projection number is directly related to implementation cost of EVC circuit, the concept of weak bit is considered and only reliable binary pattern matching is evaluated. The implementation of weak bit based on EVC circuit is also described. Simulation results show that, the performance of EVC can be significantly improved with weak bit implementation under limited projection number.