Arithmetic Optimization Algorithm (AOA) is a heuristic method developed in recent years. The original version was developed for continuous optimization problems. Its success in binary optimization problems has not yet been sufficiently tested. In this paper, the binary form of AOA (BinAOA) has been proposed. In addition, the candidate solution production scene of BinAOA is developed with the xor logic gate and the BinAOAX method was proposed. Both methods have been tested for success on well-known uncapacitated facility location problems (UFLPs) in the literature. The UFL problem is a binary optimization problem whose optimum results are known. In this study, the success of BinAOA and BinAOAX on UFLP was demonstrated for the first time. The results of BinAOA and BinAOAX methods were compared and discussed according to best, worst, mean, standard deviation, and gap values. The results of BinAOA and BinAOAX on UFLP are compared with binary heuristic methods used in the literature (TSA, JayaX, ISS, BinSSA, etc.). As a second application, the performances of BinAOA and BinAOAX algorithms are also tested on classical benchmark functions. The binary forms of AOA, AOAX, Jaya, Tree Seed Algorithm (TSA), and Gray Wolf Optimization (GWO) algorithms were compared in different candidate generation scenarios. The results showed that the binary form of AOA is successful and can be preferred as an alternative binary heuristic method.