Split inteins are powerful tools for seamless ligation of synthetic split proteins. Yet, their use remains limited because the already intricate split site identification problem is often complicated by the requirement of extein junction sequences. To address this, we augment a mini-Mu transposon-based screening approach and devise the intein-assisted bisection mapping (IBM) method. IBM robustly reveals clusters of split sites on five proteins, converting them into AND or NAND logic gates. We further show that the use of inteins expands functional sequence space for splitting a protein. We also demonstrate the utility of our approach over rational inference of split sites from secondary structure alignment of homologous proteins, and that basal activities of highly active proteins can be mitigated by splitting them. Our work offers a generalizable and systematic route towards creating split protein-intein fusions for synthetic biology.